片上网络路由评估的基于轨迹的结构可观测性框架

《Algorithms》：A Trace-Based Structural Observability Framework for Network-on-Chip Routing Evaluation

　　

传统片上网络（Network-on-Chip，NoC）评估基于聚合指标。大多数此类指标（时延、吞吐率、跳数、丢包率、能耗、缓冲区占用、热或可靠性汇总）将详细执行轨迹压缩为少数标量值。这种降维隐藏了仿真之间的空间、时间和资源级差异。研究人员提出一种熵性结构可观测性（Entropic Structural Observability）框架，用于路由无关（routing-independent）的NoC轨迹后仿真分析。该框架核心思想是将带类型的包级事件转换为已用资源上的概率分布，包括路由器、有向链路、时间窗和关键资源。最终报告构建结构签名（structural signature），包含归一化熵、有效支撑、集中度、时空互信息、分布漂移、拓扑感知空间统计、缓冲区压力度量和经典不均衡指标。分析不修改仿真轨迹，作为诊断层运行，揭示活动分布、时间依赖性、空间演化、资源压力和结构不均衡。框架在256路由器2D与3D网格拓扑上，使用确定性与自适应路由策略及多种流量模式与注入率评估，使结构签名可跨网络维度检验。结果表明不同结构体制：确定性维序路由呈广泛空间与时间离散；DyAD表现更强时空耦合与漂移；全自适应（Fully-Adaptive）呈高离散但中等时间变化的中间轮廓。

研究背景方面，在多核架构中通信渐成瓶颈，NoC以分组交换互连网络替代共享总线与集中交叉开关。周期精确与体系结构仿真器可输出时延、吞吐率等低维聚合指标，但相同聚合指标可能对应不同内部执行结构，例如可接受吞吐率可能来自少量路由器或链路的集中通信，低平均时延可能伴随强烈突发或强时间依赖空间模式，因此仅凭标量摘要会隐藏轨迹中的资源集中与结构信息。研究人员将此问题表述为聚合损失（aggregation loss），即带类型执行轨迹向标量性能度量投影时所丢失的结构信息，并提出在仿真后增加结构可观测性诊断层。

论文发表在《Algorithms》。研究人员开展的研究是：构建名为ERA的熵性结构可观测性框架，把NoC带类型包级事件转化为路由器、有向链路、时间窗、关键资源四类分布，并输出含归一化熵、有效支撑（effective support）、熵性集中度、时空互信息（mutual information，MI）、Jensen–Shannon漂移、近似几何漂移、Moran’s I、图平滑度、缓冲区压力与经典不均衡指标的多视图向量签名。其意义在于，聚合性能指标只回答执行得好不好，ERA签名回答活动在路由器空间、有向链路空间、时间维与关键资源上如何组织，从而让路由算法在某一标量上占优但存在集中、非平稳、测量边界脆弱等矛盾变得可被观察。

关键技术方法上，研究人员以Noxim生成执行证据，先作事件语义审计与有向链路重建，再把路由器活动、有向链路活动、时间窗活动与关键资源活动转为概率分布；采用活跃支撑归一化与全状态空间归一化两种熵归一化，用插件熵与Miller–Madow校正处理有限样本偏差，以置换检验判断路由器—时间窗依赖，用Jensen–Shannon散度测分布漂移，用图距离定义近似几何漂移，并引入Moran’s I与图拉普拉斯平滑度作空间基线，以Jain公平性、基尼系数、Theil指数作不均衡基线。

研究结果如下。

问题表述：聚合损失。研究人员将完整NoC执行轨迹记为T，聚合指标M(T)不是单射，存在T₁≠T₂但M(T₁)=M(T₂)，因此提出补诊断映射Φ(T)=s，s为向量签名，保留标量摘要通常丢失的空间、时间、资源维度。

设计原则。框架遵循非侵入性、轨迹接地、分布表示、多视图可观测性、归一化可解释性、互补性六原则；不修改路由与执行，依赖显式轨迹字段与拓扑描述，把活动计数转为概率分布，并同时报告活跃归一化熵与全归一化熵。

相关工作中，研究人员区分本框架与NoC监测硬件、VisualNoC或NoCVision等可视化工具、E-XY等熵感知路由、基于学习的异常检测；本工作是无监督、可解释、路由无关的后仿真结构诊断。

观察假设与轨迹模型。NoC表示为有向图G=(R,E)，路由器有坐标向量；每路由器r、有向链路e、关键资源k、时间窗w均有非负活动值；物理双向连接拆为两条有向链路以区分反向竞争。

事件语义与加权。路由器活动、有向链路活动、关键资源活动按声明事件类型与权重计算；默认全路由器活动模式回答包级活动出现在何处。

有向链路重建。有向链路表示为(r_i,r_j)；优先用显式源与下一跳，否则由输出端口与坐标推断；只计前向事件，无法唯一推断则计为未解析，并报告未解析有向链路比例，高比例时链路熵只能作部分解释。

概率分布与熵。研究人员定义路由器分布P(R)、有向链路分布P(L)、时间窗分布P(W)、关键资源分布P(C)；香农熵H=-Σp_ilog p_i，归一化熵H_norm=H/log N，有效支撑N_eff=exp(H)，熵性集中度C_H=1-H/H_max；区分全状态归一化熵H_full与活跃支撑归一化熵H_active，前者看完整状态空间覆盖率，后者看已用状态间均衡度。

有限样本估计。主用插件熵，稀疏小样本时报告Miller–Madow差；零概率状态进全支撑分母、不进活跃支撑分母；空时间窗计入时间覆盖但不构造空间分布。

时空互信息。联合分布P(R,W)与边际P(R)、P(W)得I(R;W)=Σ P(r,w)log[P(r,w)/(P(r)P(w))]；用归一化空间—时间耦合Ⅰ?，并做B次置换得经验p值，多检验下补Benjamini–Hochberg错误发现率（False Discovery Rate，FDR）摘要，效应量与显著性并列报告。

Jensen–Shannon漂移。各非空窗空间图P_w(r)，以JSD(P_w,P?)测分布变化，P?为均值分布，汇报平均JSD与最大JSD。

几何漂移。不用完整最优传输，而用活动中心c_w=Σ_ra_w(r)·coord(r)/Σ_ra_w(r)，相邻非空窗位移除以网格图直径得近似几何漂移；它只是中心位移筛查量，不能捕捉反向流与多峰重排。

经典不均衡基线。Jain公平性指数、变异系数、热点比、基尼系数、Theil指数用于解释签名，但不捕捉时空依赖。

空间基线。Moran’s I用对称物理邻接权重测空间自相关，图平滑度用图拉普拉斯L得S=1-(f^TLf)/(f^Tf)；熵、Moran’s I、图平滑度互为补充。

ERA签名。签名是向量而非单分数，含空间、有向链路、时间、关键资源熵，时空MI，JSD漂移，近似几何漂移，缓冲区压力，不均衡与空间基线；降为单标度会掩盖矛盾。

关键资源映射。256路由器有线网格中关键资源取缓冲区资源，垂直链路作拓扑特有通信资源但不进缓冲H_C；无线与RF资源未激活。缓冲区压力按平均占用比或阈值高压事件建模。

实现与验证工作流。Noxim产证据，审计后建分布、耦合、漂移、资源与不均衡量，再做范围检查、记账检查、不确定性摘要与一致性检查；可移植到BookSim或Garnet需轨迹模式适配器。

复杂度与开销。流式为O(N_events)，联合分布与MI、JSD同为O(R·W)，稀疏实现内存O(nnz)；实测代表迹约1.16×10³事件/秒，墙钟时间随事件量变化，内存随中间结构变化。

仿真配置。16×16 2D网格与8×8×4 3D网格共256路由器，路由为XY/XYZ、DyAD、Fully-Adaptive；流量含random、transpose1、shuffle、bit-reversal、butterfly、hotspot，2D另加transpose2；注入率0.001、0.003、0.006、0.009、0.012；每仿真18000周期、3000周期预热、4000周期测量边界、窗口1000周期；总计1065次运行。

全局ERA签名。维度序路由路由器熵与时间熵高、I(R;W)低，活动广布但热点下仍有高时延与缓冲压力；DyAD时间熵最低、MI与JSD最高，强时间依赖与非平稳；Fully-Adaptive高空间离散、耦合与漂移低于DyAD，呈中间体制。

流量级签名。random下XY与Fully-Adaptive高空间与链路离散，DyAD时间更集中且JSD更高；transpose下DyAD的I(R;W)高；hotspot下XY与Fully-Adaptive耦合与漂移上升，但缓冲集中与包级可用性或损失结构不同。

XY/XYZ解释。维度序路由全局分散不意味着无拥塞；hotspot中丢包与P95时延变大，问题是广覆盖叠加流量依赖型压力，而非活动塌缩到极小活跃集。

DyAD解释。保留样本有效时延低，但大量测量边界后包级指标未定义；轨迹时间结构化强，知道时间窗能显著降低路由器位置不确定性，连续空间图常变。

Fully-Adaptive解释。路由器与有向链路熵高、时间熵高于DyAD、MI较低、JSD与近似漂移高于维度序；很多流量下包级结果优于维度序，但hotspot与高负载仍出现损失或部分种子包级未定义。

诊断综合。经典指标与结构签名互补：维度序可高熵低耦合却热点高损，DyAD可样本时延低却高耦合强漂移且缺测多，Fully-Adaptive为高离散中等耦合中间类；单标度排名会丢矛盾。

不确定性与归一化。置信区间只由非NA值算；维度序高熵轮廓稳，DyAD耦合与漂移变异大，Fully-Adaptive耦合漂移不确定性一般低于DyAD。活跃归一化看已用状态均衡，全归一化看完整支撑覆盖；维度序活跃归一化高但全归一化有向链路与关键资源熵较低，DyAD全关键资源熵最低，Fully-Adaptive全关键资源熵最高。

有向链路与未解析。本战役所有前向事件可解析，故H_L、H_L,full、H_L,active来自重建有向链路而非路由器活动复制。

资源级分析。维度序平均与P95缓冲压力最高；DyAD平均缓冲压力最低但关键资源熵最低，活跃资源上更集中；Fully-Adaptive缓冲压力居中且全关键资源熵最高，缓冲资源使用更广。

窗口与事件权重敏感。路由器熵对窗口大小稳健，MI与JSD敏感：小窗显锐耦合与强漂移，大窗平滑；路由器熵对事件权重较稳，MI对事件语义敏感，故事件语义必须显式声明。

置换检验。三种路由均具统计支持的路由器—时间窗依赖，但DyAD的I(R;W)最大，维度序与Fully-Adaptive弱得多；显著性不替代效应量。

应力案例。DyAD random在PIR 0.012近似几何漂移最大，DyAD hotspot次之；Fully-Adaptive与维度序hotspot中心位移较小。

空间基线比较。维度序与Fully-Adaptive平均Moran’s I高于DyAD，图平滑度近1故全局区分弱；ERA熵与空间基线相关但不冗余。

诊断案例研究。XY+hotspot+PIR 0.012三粒种子平均时延9638.53–9769.81、P95时延15367–15511、丢包0.1587–0.1654、缓冲P95压力0.8750；标量都指严重受压，但ERA进一步定位到路由器129–133即坐标(8,1)–(8,5)构成热点路由器128即(8,0)上游Y?链133→132→131→130→129→128，X向事件46.0%–47.1%、Y向52.9%–54.0%，高压分数约0.99–1.00，I(R;W)=0.178–0.184，JSD=0.100–0.107，近似几何漂移0.045–0.055；三粒种子前五路由器与前五有向链路完全重叠，说明x=8收敛走廊是稳定结构特征而非种子偶然。

局限与效度威胁。仅两类规则256路由器网格与三类路由，不直接推广到无线NoC、故障感知路由、非规则拓扑或真实应用轨迹；合成流量用于隔离结构体制；MI需置换、熵需不确定性、近似几何漂移只是筛查；ERA可揭示集中、漂移、不均衡与持久结构，但不自证因果；跨仿真器需适配器。

讨论与结论翻译。研究人员提出ERA，一种用于NoC轨迹路由无关后仿真分析的熵性结构可观测性框架；该框架将带类型包级事件转为路由器、有向链路、时间与声明资源分布，再计算含归一化熵、有效支撑、集中度、互信息、时空耦合、Jensen–Shannon漂移、近似几何漂移、空间基线、缓冲压力与经典不均衡指标的向量签名。贡献在于把这些度量整合进带显式事件语义、有向链路重建、活跃/全归一化、资源映射、不确定性报告、敏感性分析、有限样本解释与保守解释规则的NoC专用带类型轨迹方法学。1065次运行战役在256路由器2D与3D网格上跨确定性与自适应路由、多流量、五档注入率与独立种子评估框架；结果显示跨路由、流量、负载与网络维度的不同结构签名。经典度量量化执行性能，ERA刻画活动在路由器、有向链路、时间与关键资源上的组织方式；诊断分析进一步表明持久关键结构可跨独立执行定位与复现，提供聚合性能度量单独无法给出的信息。