Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture
-
摘要:
确保片上网络(network-on-chip,NoC)中的数据传输无死锁,是NoC为多处理器片上系统(multi-processor system-on-chip,MPSoC)提供可靠通信服务的前提,决定了NoC甚至MPSoC的可用性. 现有的通用防死锁策略难以发挥出特定拓扑结构的自身特点和优势,甚至可能会增加网络延迟、功耗以及硬件复杂性. 另外,由于路由级和协议级死锁存在显著差异,现有无死锁方案较难同时解决这2类死锁问题,影响了MPSoC的可靠性. 利用基三众核架构(triplet-based many-core architecture,TriBA)中拓扑结构自身具有的哈密顿特性提出了基于同步哈密顿环的无死锁策略,该策略依据拓扑结构自身的对称轴和哈密顿边对数据传输进行分类,预防了协议级死锁并提高了数据传输速度;同时使用循环链表技术判断同一缓冲区内数据同步传输方向,消除了路由级死锁并降低了数据传输延迟. 在优化前瞻路由算法基础上,设计了基于同步哈密顿环的无死锁路由机制HamSPR(Hamiltonian shortest path routing). GEM5仿真结果表明,与TriBA现有方法相比,HamSPR在合成流量下的平均数据包延迟和功耗分别降低了8.78% ~ 65.40% 和6.94% ~ 34.15%,吞吐量提高了8.00% ~ 59.17%;在PARSEC测试集下的应用运行时间和平均数据包延迟分别最高实现了16.51%和42.75%的降低. 与2D-Mesh架构相比,TriBA在PARSEC测试集下的应用性能实现了1% ~ 10%的提升.
Abstract:Ensuring deadlock-free data transmission in the network-on-chip (NoC) is a prerequisite for providing reliable communication services for multi-processor system-on-chip (MPSoC), directly determining the availability of NoC and even MPSoC. Existing general-purpose deadlock-free strategies are oriented to arbitrary topologies, making it challenging to utilize the features and advantages of a specific topology. Moreover, these strategies may even increase network latency, power consumption, and hardware complexity. In addition, due to significant differences in the regular network between routing-level and protocol-level deadlocks, existing solutions struggle to simultaneously address both types of deadlock issues, affecting MPSoC reliability. We propose a deadlock-free strategy with synchronous Hamiltonian rings based on the inherent Hamiltonian characteristics of the triplet-based many-core architecture (TriBA). This method uses the topology’s symmetric axes and Hamiltonian edge to allocate independent store-and-forward buffers for data transmission, preventing protocol-level deadlocks and improving data transfer speed. Additionally, we design a directional determination method for data transmission within the same buffer using cyclic linked-list technology. This method ensures data independence and synchronous forward transmission, eliminates routing-level deadlocks, and reduces data transfer latency. Based on optimizing redundant calculations in look-ahead routing algorithms, we propose a deadlock-free routing mechanism called Hamiltonian shortest path routing (HamSPR) based on a synchronous Hamiltonian ring. GEM5 simulation results show that, compared with existing solutions in the TriBA, HamSPR reduces average packet latency and power consumption in synthetic traffic patterns by 18.78%−65.40% and 6.94%−34.15%, respectively, while improving throughput by 8.00%−59.17%. In the PARSEC benchmark, HamSPR achieves maximum reductions of 16.51% in application runtime and 42.75% in average packet latency, respectively. Moreover, compared with 2D-Mesh, TriBA demonstrates an application performance improvement of 1%−10% in PARSEC benchmark.
-
最近的研究表明深度神经网络(deep neural network,DNN)受到对抗攻击时表现不佳[1-3]. 当前的跟踪模型大多依赖DNN,Yan等人[4]和Nakka等人[5]也证实了基于DNN的跟踪模型受到对抗攻击时,很难成功跟踪目标. 视觉跟踪技术被广泛地应用在与安全相关的领域,如智能监控、自动驾驶等方面. 因此抵御对抗攻击具有理论研究和实际应用的重要意义. 目前有3种策略抵御对抗攻击:对抗防御,旨在使深度模型受到对抗攻击时仍能输出正确结果;对抗检测,旨在检测深度模型的输入是否受到对抗攻击;二者结合. 本文重点研究对抗检测,即检测跟踪器的输入视频序列是否为对抗输入.
跟踪领域的对抗攻击是指攻击者通过向原始视频序列中添加扰动噪声并合成对抗视频序列,导致跟踪器难以在对抗视频序列上成功地跟踪目标. 目前针对跟踪领域的对抗检测方法尚未提出. 现有的对抗检测方法[6-13]大多服务于识别领域. 它们很难直接应用到跟踪领域,其主要原因在于:1)处理对象不同. 识别任务涉及的是互不相关的静态图像,检测的对象也是独立图像. 跟踪任务处理的是视频序列,视频帧之间的相关性较大,检测的对象是视频序列. 2)攻击方式不同. 对于识别任务,通常只需要向单个图像中添加扰动噪声,就能实现攻击效果;对于跟踪任务,通常需要向整个视频序列中添加扰动噪声,才能实现显著的攻击效果. 针对如何设计适用于跟踪任务的对抗检测方案,本文认为实现对抗检测的关键在于要明确攻击者是如何攻击跟踪器的. 为了有效地攻击跟踪器同时视觉上欺骗用户,跟踪领域的对抗攻击方法[4-5,14-24]生成的扰动噪声几乎是视觉不可见. 如图1所示,原始图像和带有扰动噪声的对抗图像,视觉上几乎没有差异,但扰动噪声却能成功地干扰跟踪器(虚线框表示精准地定位到目标,实线框则远离目标). 这说明扰动噪声对人眼视觉不可见但对深度跟踪模型是“可见的”. 那么视觉上,扰动噪声被添加在图像的什么地方需要探索.
生物学指出人眼只能观察到特定频域内的信息. 受此启发,首先借助离散傅里叶变换(discrete fourier transform,DFT)理论证明了扰动噪声主要被添加在图像的中高频段,这些是视觉难以捕捉的频域, 但跟踪模型却对其较为敏感. 为了佐证低频段受扰动噪声影响较小,定量地研究了攻击前后视频序列各频段分量的贡献,并分析出低频段分量对跟踪性能的贡献最大且受对抗攻击的影响最小. 基于上述的理论证明和定量研究,论文以SiamRPNpp跟踪器[25]为主要研究对象,设计了一个简单有效的对抗检测框架,主要包含频域分解模块、判别模块、目标跟踪器及其同构同参的镜像跟踪器. 频域分解模块负责提取视频序列的低频段分量,并将其作为镜像跟踪器的输入;而目标跟踪器则以视频序列的全频段分量为输入;判别模块通过对比2个跟踪器的输出差异性,判定输入视频序列是否为对抗输入. 该检测框架无需使用对抗样本进行对抗训练,即可有效地检测多种对抗攻击,且可以灵活地集成到多个跟踪器.
论文的贡献主要包括:
1)提出了适用于跟踪任务的对抗检测框架,无需对抗训练. 仅通过对比视频序列不同频段分量间的跟踪性能差异性,即可有效地检测输入视频序列是否为对抗输入.
2)理论证明了跟踪领域的对抗攻击方法主要将扰动噪声添加在视频序列的中高频段;并定量地分析出视频序列的低频段分量对跟踪性能的贡献最大且受对抗攻击的影响最小.
3)将检测框架灵活地集成到多个跟踪器,大量的实验结果表明检测框架不仅能够有效地检测主流的对抗攻击而且对跟踪器的原始性能影响较小.
1. 相关工作
1.1 跟踪领域的对抗攻击
自Wiyatno等人[14]于2019年首次将对抗纹理应用到视频序列并成功地干扰跟踪过程以来,近些年陆续涌现出许多对抗攻击方法[4-5,15-24]. 它们通过将扰动噪声添加到原始视频序列,导致跟踪器难以在对抗视频序列上跟踪到真实目标,极大地降低了跟踪器的跟踪性能. 按照扰动噪声的生成方式,这些攻击方法主要分为基于深度网络的攻击方法和基于迭代优化的攻击方法. 前者通过离线训练一个基于深度网络的扰动生成器,在线向原始视频序列中添加扰动噪声. 例如,Yan等人[4]提出的冷却收缩攻击(cooling-shrinking attack,CSA)以及Nakka等人[5]提出的时间转移扰动攻击(temporally-transferable perturbations,TTP)利用跟踪器的输出建立了有关置信分数和边框偏移的损失函数,然后离线训练基于深度网络的生成器. 在攻击过程中,生成器以视频帧为输入生成扰动噪声,并将其叠加到对应的视频帧作为跟踪器的输入,以此降低其跟踪性能. 后者则直接以降低跟踪性能为目标,通过迭代优化的方式改变原始视频帧上的像素值. 例如,Guo等人[15]提出的空间感知的在线增量攻击(spatial-aware online incremental attack,Spark),基于符号梯度下降迭代法提出了空间感知在线增量攻击方法,通过向视频序列添加增量扰动,有效地干扰了跟踪器的跟踪过程.
尽管这些攻击方法都是向视频序列中添加扰动噪声,但不同的是,有些方法向视频序列的每一帧添加扰动噪声,如CSA[4],TTP[5],Spark[15];有些方法仅向视频序列的初始帧添加扰动噪声,如One-shot [16],OOA[17];有些方法则是向视频序列中添加小尺寸扰动补丁,如UTA[18],APA[19]. 本文以视频序列为检测单元,主要检测那些向整个视频序列添加扰动噪声的攻击方法.
1.2 离散余弦变换
离散余弦变换(discrete cosine transform,DCT)常用于对信号进行有损压缩. 利用2维DCT变换提取视频序列的低频段分量. 2维DCT变换及其逆变换如式(1)和式(2)所示:
\begin{split} {\boldsymbol{X}}(u,v) =\;& {\sigma _u}{\sigma _v}\sum\limits_{m = 0}^{M - 1} {\sum\limits_{n = 0}^{N - 1} {{\boldsymbol{x}}(m,n)} } \times \\ &\cos \left[\frac{{(m + 0.5){\text{π }}}}{M}u\right]\cos \left[\frac{{(n + 0.5){\text{π }}}}{N}v\right], \end{split} (1) \begin{split} {\boldsymbol{x}}(m,n) =\;& \sum\limits_{u = 0}^{M - 1} {\sum\limits_{v = 0}^{N - 1} {{\sigma _u}{\sigma _v}{\boldsymbol{X}}(u,v)} } \times \\ &\cos \left[\frac{{(m + 0.5){\text{π }}}}{M}u\right]\cos \left[\frac{{(n + 0.5){\text{π }}}}{N}v\right], \end{split} (2) \begin{split} & {{\sigma _u} = \left\{ {\begin{aligned} &{1/\sqrt M ,{\text{ }}u = 0,} \\ &{\sqrt {2/M} ,{\text{ }}u \ne 0,} \end{aligned}} \right.} \\ &{{\sigma _v} = \left\{ {\begin{aligned} &{1/\sqrt N ,{\text{ }}v = 0.} \\ &{\sqrt {2/N} ,{\text{ }}v \ne 0.} \end{aligned}} \right.} \end{split} (3) 经过DCT变换后,空域图像 x \in {\mathbb{R}^{M \times N}} 与其频域系数矩阵 {\boldsymbol{X}} \in {\mathbb{R}^{M \times N}} 具有相同尺寸. 为了便于下文表述,将频域系数矩阵 {\boldsymbol{X}} 的频段范围[0~M]和[0~N]归一化为[0~1]. 例如,M=N=250,归一化后,0.1频段步长代表的实际频段步长为25;[0~1]表示全频段分量即完整图像.
2. 目标跟踪的对抗检测方法
2.1 跟踪过程和攻击过程简要描述
给定视频序列 \mathcal{V} = \{ {{\boldsymbol{I}}_t}\} _{t = 1}^T ,图2以SiamRPNpp跟踪器[25]为例展示了跟踪过程和攻击过程. 在跟踪过程中,首先从初始帧 {{\boldsymbol{I}}_1} 中裁剪出模板图像 {\boldsymbol{z}} ,用于初始化跟踪器 \mathcal{T} ,然后从视频帧 {{\boldsymbol{I}}_t} 中裁剪出搜索图像 {x_t}, t = 2,3,…,{\text{T}} ,跟踪器 \mathcal{T} 实际是在搜索图像 {x_t} 上跟踪目标. 对于第 t 帧,模板图像 {\boldsymbol{z}} 和搜索图像 {x_t} 首先通过主干网络提取通用特征进行相似度匹配,并得到相似度图 E ,然后将 E 送入区域候选网络(region proposal network,RPN)[26]用于预测分类图 \{ s_t^i \in {\boldsymbol{S}}\} _{i = 1}^N 和回归图 \{ {\boldsymbol{b}}_t^i \in B\} _{i = 1}^N ,最后取最大置信分数 s_t^m 并将其对应的预测边框 {\boldsymbol{b}}_t^m 作为第 t 帧的跟踪结果,即 (s_t^m,b_t^m) = \mathcal{T}(z,{x_t}) ,其中 m = \arg {\text{ }}max\{ s_t^i\} _{i = 1}^N . 当预测边框 b_t^m 与标签边框 b_t^{{gt} } 的交并比IoU(intersection of union)超过阈值 \theta ,即 {{\varOmega }}({\boldsymbol{b}}_t^m,{\boldsymbol{b}}_t^{{gt} }) > \theta ,则表示跟踪器在第 t 帧上成功地跟踪到目标,其中 {{\varOmega }}( \cdot ) 表示计算2个边框间的交并比. 对于整个数据集,通常使用不同阈值下成功率的曲线面积AUC(area under curve)来衡量跟踪器在整个数据集上的跟踪性能,其值越大说明跟踪性能越好.
攻击过程伴随着跟踪过程. 在攻击过程中,攻击者 \mathcal{A} 通常首先向原始模板图像 {\boldsymbol{z}} 中添加扰动噪声,合成对抗模板图像 {\boldsymbol{\tilde z}} ,用于干扰跟踪器的初始化,然后再向搜索图像 {x_t} 中添加扰动噪声,合成对抗搜索图像 {\tilde x_t} ,用于干扰其正常跟踪. 跟踪器以对抗模板图像 {\boldsymbol{\tilde z}} 和对抗搜索图像 {\tilde x_t} 为输入,会输出较差的跟踪结果,即 (\tilde s_t^m,\tilde b_t^m) = \mathcal{T}(\tilde z,{\tilde x_t}) , m = \arg {\text{ }}max\{ \tilde s_t^i\} _{i = 1}^N . 预测边框 \tilde b_t^m 与标签边框 b_t^{{gt} } 之间的交并比很小,表示跟踪失败. 算法1以伪代码的形式描述了跟踪和攻击过程.
算法1. 跟踪过程与攻击过程算法描述.
输入:视频序列 \mathcal{V} = \{ {{\boldsymbol{I}}_t}\} _{t = 1}^T ,跟踪器 \mathcal{T} ,攻击者 \mathcal{A} ;
输出:跟踪结果.
跟踪过程:
① 从初始帧 {{\boldsymbol{I}}_1} 中裁剪出模板图像 {\boldsymbol{z}} ;
② 用 {\boldsymbol{z}} 初始化跟踪器 \mathcal{T} ;
③ for t = 2,3,…,T do 从视频帧 {{\boldsymbol{I}}_t} 中裁剪出搜索图 像 {{\boldsymbol{x}}_t} ; \mathcal{T} 以模板图像 {\boldsymbol{z}} 和搜索图像 {{\boldsymbol{x}}_t} 为输入; 执行跟踪任务,即 (s_t^m,b_t^m) = \mathcal{T}(z,{x_t}) ;输出每 一帧的跟踪结果 {\boldsymbol{b}}_t^m,t = 2,3,…,T ;
④ end for
攻击过程:
① 向 {\boldsymbol{z}} 中添加扰动,得到对抗模板图像 {\boldsymbol{\tilde z}} ;
② 用 {\boldsymbol{\tilde z}} 初始化跟踪器 \mathcal{T} ;
③ for t = 2,3,…,T do 向 {{\boldsymbol{x}}_t} 中添加扰动,得到对抗 搜索图像 {{\boldsymbol{\tilde x}}_t} ; \mathcal{T} 以 {\boldsymbol{\tilde z}} 和 {{\boldsymbol{\tilde x}}_t} 为输入;执行跟踪任 务,即 (\tilde s_t^m,\tilde b_t^m) = \mathcal{T}(\tilde z,{\tilde x_t}) ;输出每一帧的跟踪 结果 {\boldsymbol{\tilde b}}_t^m,t = 2,3,…,T ;
④ end for
2.2 扰动存在于中高频段的理论证明
对抗攻击方法通常在扰动生成损失函数中增加约束项限定扰动噪声不超过阈值 \varepsilon ,如 ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_2} \leqslant \varepsilon [4-5]和 ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_\infty } \leqslant \varepsilon [15],以此确保扰动噪声视觉不可见. 本节推断扰动噪声主要被添加在图像的中高频段并借助DFT证明上述推论.
定理1. 假设原始图像 {\boldsymbol{x}} \in {\mathbb{R}^{M \times N}} 和对抗图像 \tilde {\boldsymbol{x}} \in {\mathbb{R}^{M \times N}} ,可以得出以下推论:
\frac{1}{D}|{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| \leqslant ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_\infty } \leqslant \varepsilon , (4) \frac{1}{{\sqrt D }}|{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| \leqslant ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_2} \leqslant \varepsilon , (5) 式(6)和式(7)表示傅里叶变换 f 和其逆变换 {f^{ - 1}} :
{{\boldsymbol{X}}_k} = f{({\boldsymbol{x}})_k} = \sum\limits_{j = 0}^{D - 1} {{{\boldsymbol{x}}_j}{{\text{e}}^{ - {\text{i}}\tfrac{{2{\text{π }}}}{D}kj}}} , (6) {{\boldsymbol{x}}_j} = {f^{ - 1}}{(X)_j} = \frac{1}{D}\sum\limits_{k = 0}^{D - 1} {{X_k}{{\text{e}}^{{\text{i}}\tfrac{{2{\text{π }}}}{D}kj}}} , (7) 其中 {X_0} 和 {\tilde X_0} 分别是 k = 0 的傅里叶系数. {\text{i}} 是复数因子, {{\text{i}}^2} = - 1 , D = {\text{M}} \times N . 在证明式(4)之前,先引入式(8):
\begin{split} \sum\limits_{j = 0}^{D - 1} {{{\text{e}}^{{\text{i}}j\omega }}} =\;& 1 + {{\text{e}}^{{\text{i}}\omega }} + {{\text{e}}^{{\text{i}}2\omega }} + … + {{\text{e}}^{{\text{i}}(D - 1)\omega }}= \\ &\frac{{1 - {{\text{e}}^{{\text{i}}D\omega }}}}{{1 - {{\text{e}}^{{\text{i}}\omega }}}} = \frac{{{{\text{e}}^{{\text{i}}D\omega /2}}({{\text{e}}^{ - {\text{i}}D\omega /2}} - {{\text{e}}^{{\text{i}}D\omega /2}})}}{{{{\text{e}}^{{\text{i}}\omega /2}}({{\text{e}}^{ - {\text{i}}\omega /2}} - {{\text{e}}^{{\text{i}}\omega /2}})}} =\\ &\frac{{\sin (D\omega /2)}}{{\sin (\omega /2)}}{{\text{e}}^{{\text{i}}\omega (D - 1)/2}}, \end{split} (8) 令 \omega = \dfrac{{2{\text{π }}}}{D}k ,则式(8)可以表示为
\sum\limits_{j = 0}^{D - 1} {{{{\mathrm{e}}}^{{i}(2k{\text{π}}/D)j}}} = \frac{{\sin (k{\text{π}})}}{{\sin (k{\text{π}}/D)}}{{{\mathrm{e}}}^{{i}k{\text{π}}(D - 1)/D}}, (9) 当 k = {\text{D}} 或 k = 0 时, \displaystyle\sum\limits_{j = 0}^{D - 1} {{{{\mathrm{e}}}^{{i}(2k{\text{π}}/D)j}}} = D ;当 k \ne D 且 k \ne 0 时, \displaystyle\sum\limits_{j = 0}^{D - 1} {{{{\mathrm{e}}}^{{i}(2k{\text{π}}/D)j}}} = 0 .
式(4)的具体推导过程如下:
\begin{split} &\left|\right|{\boldsymbol{x}}-\tilde{{\boldsymbol{x}}}|{|}_{\infty }\ge \frac{1}{D}||{\boldsymbol{x}}-\tilde{{\boldsymbol{x}}}|{|}_{1}=\frac{1}{D}{\displaystyle \sum _{j=0}^{D-1}|{{\boldsymbol{x}}}_{j}-{\tilde{{\boldsymbol{x}}}}_{j}|}=\\ &\frac{1}{D}{\displaystyle \sum _{j=0}^{D-1}|{f}^{-1}{({\boldsymbol{X}})}_{j}-{f}^{-1}{(\tilde{\boldsymbol{X}})}_{j}|}= \end{split} \begin{split} &\frac{1}{D}{\displaystyle \sum _{j=0}^{D-1}|\frac{1}{D}{\displaystyle \sum _{k=0}^{D-1}{{\boldsymbol{X}}}_{k}{\text{e}}^{\text{i}\tfrac{2\text{π}}{D}kj}}-\frac{1}{D}{\displaystyle \sum _{k=0}^{D-1}{\tilde{{\boldsymbol{X}}}}_{k}{\text{e}}^{\text{i}\tfrac{2\text{π}}{D}kj}}|}=\\ &\frac{1}{{D}^{2}}{\displaystyle \sum _{j=0}^{D-1}\left|{\displaystyle \sum _{k=0}^{D-1}({{\boldsymbol{X}}}_{k}-{\tilde{{\boldsymbol{X}}}}_{k}){\text{e}}^{\text{i}\tfrac{2\text{π}}{D}kj}}\right|}\ge\\ & \frac{1}{{D}^{2}}|{\displaystyle \sum _{j=0}^{D-1}{\displaystyle \sum _{k=0}^{D-1}({{\boldsymbol{X}}}_{k}-{\tilde{{\boldsymbol{X}}}}_{k}){\text{e}}^{\text{i}\tfrac{2\text{π}}{D}kj}}|}=\\ &\frac{1}{{D}^{2}}\left|{\displaystyle \sum _{k=0}^{D-1}({{\boldsymbol{X}}}_{k}-{\tilde{{\boldsymbol{X}}}}_{k})}{\displaystyle \sum _{j=0}^{D-1}{\text{e}}^{\text{i}\tfrac{2\text{π}}{D}kj}}\right|=\\ &\frac{1}{{D}^{2}}\times D|{{\boldsymbol{X}}}_{0}-{\tilde{{\boldsymbol{X}}}}_{0}|\to 式(9)=\\ &\frac{1}{D}|{{\boldsymbol{X}}}_{0}-{\tilde{{\boldsymbol{X}}}}_{0}|. \end{split} (10) 因为L2范式为 ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_2} = \sqrt {\displaystyle\sum\limits_{j = 0}^{D - 1} {|{{\boldsymbol{x}}_j} - {{{\boldsymbol{\tilde x}}}_j}{|^2}} } ,其与L1范式的关系可表示为
||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_1} \leqslant \sqrt D ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_2}, (11) 由式(10)可得 ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_1} \geqslant |{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| ,因此可以得到
|{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| \leqslant \sqrt D ||{\boldsymbol{x}} - {\boldsymbol{\tilde x}}|{|_2}, (12) 完成式(5)的证明. 证毕.
由式(4)和式(5)可以发现,扰动噪声变化的下限边界 \varepsilon 只与频域中 {{k}} = 0 的傅里叶系数有关,即低频段相关. 更确切地说,下限边界 \varepsilon 与 |{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| 呈正相关. 如果扰动噪声被添加在图像的低频段,则 |{{\boldsymbol{X}}_0} - {{\boldsymbol{\tilde X}}_0}| 和 \varepsilon 会变大,扰动损失也会变大. 这违背了攻击模型收敛和扰动视觉不可见的原则. 因此,为了使扰动生成损失和扰动噪声尽可能小,对抗攻击方法将扰动噪声主要添加在图像的中高频段内.
2.3 频段分量贡献的定量研究
本节通过经验性实验定量地分析视频序列的各频段分量对跟踪性能的贡献和受对抗攻击的影响.
攻击前各频段分量的跟踪性能对比. 首先以0.1为频段步长将OTB2015数据集[27]和UAV123数据集[28]中的原始视频序列分解为多个频段分量,然后SiamRPNpp在原始视频序列的各个频段分量上执行跟踪任务. 图3展示了攻击前SiamRPNpp在OTB2015和UAV123数据集各频段分量上的跟踪结果,“0~1”表示全频段分量. 图3中的AUC表示攻击前跟踪器在各频段分量上的跟踪性能;D_AUC表示跟踪器在各频段分量上的AUC与在全频段分量上的AUC之间的差值. 受攻击前,跟踪器在全频段分量上的AUC值较大. 因此,任意频段分量上的D_AUC值越小,表明跟踪器在该频段分量上的跟踪性能与在全频段分量上的跟踪性能间的差异越小,说明该频段分量对跟踪器的跟踪性能贡献越大. 可以看出,受攻击前,[0~0.1]频段分量对跟踪器的跟踪性能贡献最大.
攻击后各频段分量的跟踪性能对比. 首先利用CSA[4]和TTP[5]向OTB2015和UAV123数据集的所有视频序列中添加扰动噪声,生成对抗视频序列;然后以0.1为频段步长分解这些对抗视频序列;最后SiamRPNpp在对抗视频序列的各个频段分量上执行跟踪任务. 图4和图5分别表示受CSA和TTP攻击后,SiamRPNpp在OTB2015和UAV123数据集各频段分量上的跟踪结果,AUC表示攻击后跟踪器在各频段分量上的跟踪性能;D_AUC表示跟踪器在各频段分量上的AUC与在全频段分量上的AUC之间的差值. 受攻击后,跟踪器在全频段分量上的AUC值较小. 因此,任意频段分量上的D_AUC值越大,表明跟踪器在该频段分量上的跟踪性能与在全频段分量上的跟踪性能之间的差异越大,说明该频段分量受对抗攻击的影响越小. 可以看出,受攻击后,[0~0.1]频段分量受对抗攻击的影响最小.
上述实验表明视频序列被攻击前,跟踪器在原始视频序列的低频段和全频段分量上的跟踪性能差异较小;视频序列被攻击后,因全频段包含带有扰动噪声的中高频段,所以跟踪器在对抗视频序列的低频段和全频段分量上的跟踪性能差异较大,这也是本文方法的检测机制.
2.4 基于频段跟踪性能差异的对抗检测框架
3.2节的理论证明和3.3节的定量分析阐述了2个观点:1)扰动噪声主要存在于图像的中高频段;2)低频段分量对跟踪性能的贡献最大且受对抗攻击的影响最小. 受此启发,提出了基于频段跟踪性能差异的对抗检测框架,如图6所示. 通过将目标跟踪器替换为指定的跟踪模型,即可灵活地实现检测框架与该跟踪模型的集成,从而协助其检测对抗输入. 给定待检测的视频序列 \mathcal{V} = \{ {{\boldsymbol{I}}_t}\} _{t = 1}^T . 首先,对视频序列 \mathcal{V} 的初始帧 {{\boldsymbol{I}}_1} 进行裁剪,得到全频模板图像 {\boldsymbol{z}} ;使用频域分解模块,对 {\boldsymbol{z}} 进行频域分解,得到低频模板图像 {\boldsymbol{\hat z}} ,即 {\boldsymbol{\hat z}} = \psi ({\boldsymbol{z}}) ,其中 \psi ( \cdot ) 表示DCT操作;使用 {\boldsymbol{z}} 和 {\boldsymbol{\hat z}} 分别初始化目标跟踪器 \mathcal{T} 和镜像跟踪器 {\mathcal{T}_{os}} . 然后,在后续跟踪过程中,对视频序列 \mathcal{V} 的视频帧 {{\boldsymbol{I}}_t},t = 2,3,…,T 进行裁剪,得到全频搜索图像 {{\boldsymbol{x}}_t} ;使用频域分解模块,对 {{\boldsymbol{x}}_t} 进行频域分解,得到低频搜索图像 {{\boldsymbol{\hat x}}_t} ,即 {{\boldsymbol{\hat x}}_t} = \psi ({{\boldsymbol{x}}_t}) ;目标跟踪器 \mathcal{T} 和镜像跟踪器 {\mathcal{T}_{{os} }} 分别在全频搜索图像 {{\boldsymbol{x}}_t} 和低频搜索图像 {{\boldsymbol{\hat x}}_t} 上执行跟踪任务,得到 (s_t^m,{\boldsymbol{b}}_t^m) = \mathcal{T}({\boldsymbol{z}},{{\boldsymbol{x}}_t}) 和 (\hat s_t^m,{\boldsymbol{\hat b}}_t^m) = {\mathcal{T}_{os}}({\boldsymbol{\hat z}},{{\boldsymbol{\hat x}}_t}) . 最后,计算所有全频搜索图像上的置信分数和交并比均值,即 SC = Ave\{ s_t^m\} _{t = 2}^T 和 IoU = Ave\{ {{\varOmega }}({\boldsymbol{b}}_t^{{gt} },{\boldsymbol{b}}_t^m)\} _{t = 2}^T , Ave( \cdot ) 表示计算平均值;计算所有低频搜索图像上的置信分数和交并比均值,即 S{C_l} = Ave\{ \hat s_t^m\} _{t = 2}^T 和 Io{U_l} = Ave\{ {{\varOmega }}({\boldsymbol{b}}_t^{{gt} },{\boldsymbol{\hat b}}_t^m)\} _{t = 2}^T ;判别模块则以 (SC,IoU) 和 (S{C_l},Io{U_l}) 为输入,判定当前视频序列 \mathcal{V} 属于对抗输入还是原始输入.
检测机理. 根据3.3节的定量研究,低频段分量的跟踪性能最能代表全频段分量. 所以当输入为原始视频序列,理论上目标跟踪器和镜像跟踪器的跟踪性能差异较小. 根据3.2节的理论证明,扰动噪声主要被添加在中高频段,低频段信息受扰动的影响最小. 所以当输入为对抗视频序列,以全频段分量为输入的目标跟踪器受影响程度远大于以低频段分量为输入的镜像跟踪器,理论上目标跟踪器和镜像跟踪器的跟踪性能差异较大.
频域分解模块. 该模块由2维DCT及其逆变换组成,以全频图像为输入,通过频域分解和重构,提取低频图像.
目标跟踪器和镜像跟踪器. 这2个跟踪器共享结构和参数. 目标跟踪器以全频段视频序列为输入,即全频模板图像和全频搜索图像;镜像跟踪器以低频段视频序列为输入,即低频模板图像和低频搜索图像.
判别模块. 该模块主要包含4个判别条件. 通过对比目标跟踪器和镜像跟踪器分别在全频段视频序列和低频段视频序列上的跟踪性能,即 (SC,Io{\text{U}}) 和 (S{C_l},Io{{\text{U}}_l}) ,判定当前输入视频序列属于对抗输入还是原始输入.
在跟踪任务中,置信分数和交并比直接反映了跟踪器目标定位和边框预测的准确性. 因此,将整个视频序列的置信分数和交并比均值作为判别指标. 一方面,未受攻击时,全频段和低频段视频序列的跟踪性能差距较小;受到攻击后,全频段和低频段视频序列的跟踪性能差距较大. 因此,设置2个机理判别条件,即C1: |IoU - Io{U_l}| \gt a1 ,C2: |SC - S{C_l}| \gt a2 . 另一方面,考虑到跟踪器在一些原始视频序列上本就表现不佳,以及跟踪器并非在所有对抗视频序列上都表现较差等情况,设置2个区间判别条件,即C3: IoU \gt a3 ,C4: IoU \lt a4 .
规定如果C3成立,则判定当前输入视频序列为原始输入;如果C4成立,则判定当前输入视频序列为对抗输入;如果C1或C2成立,则判定当前输入视频序列为对抗输入,否则判定为原始输入.
算法2以伪代码的形式展示了对抗检测过程.
算法2. 基于频段跟踪性能差异的检测流程.
输入:视频序列 \mathcal{V} = \{ {{\boldsymbol{I}}_t}\} _{t = 1}^T ,目标跟踪器 \mathcal{T} 及其镜像跟踪器 {\mathcal{T}_{{os} }} ;
输出:判别结果.
① 从初始帧 {{\boldsymbol{I}}_1} 裁剪出全频模板图像 {\boldsymbol{z}} ;
② 从 {\boldsymbol{z}} 中分解出低频模板图像 {\boldsymbol{\hat z}} = \psi ({\boldsymbol{z}}) ;
③ 用 {\boldsymbol{z}} 和 {\boldsymbol{\hat z}} 分别初始化 \mathcal{T} 和 {\mathcal{T}_{os}} ;
④ for t = 2,3,…,T do 从视频帧 {{\boldsymbol{I}}_t} 裁剪出全频搜索 图像 {{\boldsymbol{x}}_t} ;从 {{\boldsymbol{x}}_t} 分解出低频搜索图像 {{\boldsymbol{\hat x}}_t} = \psi ({{\boldsymbol{x}}_t}) ; \mathcal{T} 执行跟踪任务 (s_t^m,{\boldsymbol{b}}_t^m) = \mathcal{T}({\boldsymbol{z}},{{\boldsymbol{x}}_t}) ; {\mathcal{T}_{os}} 执行 跟踪任务 (\hat s_t^m,{\boldsymbol{\hat b}}_t^m) = {\mathcal{T}_{os}}({\boldsymbol{\hat z}},{{\boldsymbol{\hat x}}_t}) ;
end for
⑤ 计算全频视频帧的置信分数和交并比均值, SC = Ave\{ s_t^m\} _{t = 2}^T , IoU = Ave\{ {{\varOmega }}({\boldsymbol{b}}_t^{{gt} },{\boldsymbol{b}}_t^m)\} _{t = 2}^T ;
⑥ 计算低频视频帧的置信分数和交并比均值, S{C_l} = Ave\{ \hat s_t^m\} _{t = 2}^T , Io{U_l} = Ave\{ {{\varOmega }}({\boldsymbol{b}}_t^{{gt} },{\boldsymbol{\hat b}}_t^m)\} _{t = 2}^T ;
⑦ 判定视频序列是否为对抗输入:
if {\text{IoU}} \gt a3
判定视频序列为原始输入;
else if IoU \lt a4
判定视频序列为对抗输入;
else if |IoU - Io{U_l}| \gt a1 or |SC - S{C_l}| \gt a2
判定视频序列为对抗输入;
else
判定视频序列为原始输入;
end if
3. 实验及分析
所有实验均在PyTorch软件平台和NVIDIA RTX3090 GPU硬件设备上仿真. 对于频域分解模块,所提取的低频分量范围设置为[0~0.1]. 对于判别模块,判别阈值设置为 a1 = 0.1 , a2 = 0.1 , a3 = 0.5 , a4 = 0.1 . 4.6节专门进行了阈值选择实验,以验证阈值选定的合理性. 对于目标跟踪器,以SiamRPNpp为主要研究对象,但在4.5节中,又专门将检测框架直接集成到其他跟踪器,以验证检测框架的泛化性能. 一方面,CSA[4],TTP[5],Spark[15]是当前主流对抗攻击方法的代表;另一方面,它们的攻击策略能够有效地降低SiamRPNpp跟踪器的跟踪性能. 因此,本文将CSA,TTP和Spark视为主要的检测对象.
3.1 数据集和检测性能评价指标
目前缺少专门用于检测对抗攻击的数据集,因此本文效仿识别领域的对抗检测做法. 在原始跟踪数据集的基础上构造用于验证对抗检测方法的混合数据集. 所使用的原始跟踪数据集包括OTB2015数据集[27]包含100个视频序列;UAV123数据集[28]包含123个视频序列;LaSOT数据集[29]包含280个视频序列. 为了构造混合数据集,利用对抗攻击方法CSA[4],TTP[5],Spark[15]分别向原始跟踪数据集的视频序列中添加扰动噪声,生成相应的对抗视频序列. 另外,考虑到对抗检测方法需要同时具备判别原始输入和对抗输入的能力,因此,混合数据集不仅包含原始视频序列还包含对抗视频序列. 例如,混合数据集OTB2015*包含100个原始视频序列和100个对抗视频序列;混合数据集UAV123*包含123个原始视频序列和123个对抗视频序列;混合数据集LaSOT*包含280个原始视频序列和280个对抗视频序列.
采用检测精度P(detection precision),召回率R(recall)和F1分数作为检测性能的评价指标,P=TP/(TP+FP),R=TP/(TP+FN),F1=2P×R/(P+R). TP表示对抗视频序列被判定为对抗输入;TN表示原始视频序列被判定为原始输入;FP表示原始视频序列被判定为对抗输入;FN表示对抗视频序列被判定为原始输入. 在跟踪任务中,通常使用AUC,精确度Pre(precision)和归一化精确度Npre(norm precision)评估跟踪器的跟踪性能. 为了衡量检测框架对跟踪器的影响,基于上述3个跟踪性能评估指标,又提出了∆AUC,∆Pre和∆Npre用于评估检测框架对跟踪器原始性能的影响. 例如,∆AUC表示原始跟踪器在原始跟踪数据集上的AUC指标与集成了检测框架的跟踪器在混合数据集上的AUC指标之间的差值. ∆AUC越小说明检测框架不仅能够有效地检测对抗攻击,而且对跟踪器的原始性能影响越小. 表1展示了所使用的数据集以及相关的性能评估指标.
表 1 数据集及评估指标Table 1. Datasets and Evaluation Metrics原始数据集 视频序列 跟踪性能评估指标 OTB2015 100 AUC,Pre,Npre UAV123 123 LaSOT 280 混合数据集 视频序列 检测性能评估指标 OTB2015* 200 P,R,F1,∆AUC, ∆Pre,∆Npre UAV123* 246 LaSOT* 560 3.2 检测CSA对抗攻击
为了验证检测方法的有效性,本节将检测框架(detection framework,DF)集成到SiamRPNpp跟踪器(缩写为SiamRPNpp+DF),并在由CSA构造的混合数据集OTB2015*,UAV123*,LaSOT*上执行跟踪任务,以此实现对CSA攻击的检测,检测结果如表2所示:
表 2 CSA攻击下的检测性能Table 2. Detection Performance Under CSA Attacks混合数据集 P/% R/% F1/% ∆AUC ∆Pre ∆Npre OTB2015* 97.55 98.68 98.11 0.028 0.018 0.025 UAV123* 95.24 96.99 96.10 0.018 0.006 0.008 LaSOT* 94.91 99.64 97.21 0.009 0.016 0.004 由表2可知,检测框架能够有效地检测出输入视频序列是否受到CSA对抗攻击. 在混合数据集OTB2015*,UAV123*,LaSOT*上的检测精度,分别高达97.55%,95.24%,94.91%. 高精度的检测性能得益于攻击前后的频段跟踪性能,存在较大的差异. 此外,∆指标表明检测框架集成到SiamRPNpp跟踪器对其的原始跟踪性能影响微乎其微. 例如,SiamRPNpp+DF跟踪器在OTB2015*数据集上的AUC性能与SiamRPNpp跟踪器在OTB2015数据集上的AUC性能差距仅有0.028. 这主要得益于检测框架能够精准地判别对抗视频序列,使其不参与到跟踪器的跟踪性能评估.
3.3 检测TTP对抗攻击
本节使用SiamRPNpp+DF跟踪器在由TTP构造的混合数据集OTB2015*,UAV123*,LaSOT*上执行跟踪任务,以此实现对TTP攻击的检测,检测结果如表3所示:
表 3 TTP攻击下的检测性能Table 3. Detection Performance Under TTP Attacks混合数据集 P/% R/% F1/% ∆AUC ∆Pre ∆Npre OTB2015* 97.73 93.48 95.56 0.021 0.030 0.025 UAV123* 95.12 91.61 93.32 0.025 0.015 0.036 LaSOT* 93.38 94.96 94.16 0.008 0.004 0.016 在面对TTP攻击时,检测框架能够在混合数据集OTB2015*,UAV123*,LaSOT*上分别取得97.73%,95.12%,93.38%的检测精度. 这说明检测框架对TTP对抗攻击也具备较好的检测性能. 这是因为TTP和CSA都属于基于深度网络的对抗攻击方法,它们都是使用扰动生成器生成扰动噪声并将其添加到图像的中高频段内. 所以本文基于频段跟踪性能差异的检测框架也能有效地检测出TTP攻击. 此外,较小的∆指标表明,检测框架对SiamRPNpp的原始跟踪性能影响很小. 例如,SiamRPNpp+DF跟踪器在UAV123*数据集上的Pre性能与SiamRPNpp跟踪器在UAV123数据集上的Pre性能差距仅为0.015.
3.4 检测Spark对抗攻击
为了检测Spark攻击,本节使用SiamRPNpp+DF跟踪器在由Spark构成的混合数据集OTB2015*,UAV123*,LaSOT*上执行跟踪任务,检测结果如表4所示:
表 4 Spark攻击下的检测性能Table 4. Detection Performance Under Spark Attacks混合数据集 P/% R/% F1/% ∆AUC ∆Pre ∆Npre OTB2015* 96.37 98.57 97.46 0.064 0.019 0.029 UAV123* 92.48 95.68 94.05 0.055 0.014 0.017 LaSOT* 96.86 98.74 97.79 0.067 0.074 0.081 由表4可知,检测框架在混合数据集OTB2015*,UAV123*,LaSOT*数据集上的召回率,分别高达98.57%,95.68%,98.74%. 高召回率的检测性能,一方面得益于视频序列受Spark攻击前后,跟踪器在全频段和低频段的跟踪性能差异更为明显,另一方面得益于本文设置的精细化判别条件. 然而,精细化的判别准则也使得判别模块出现了过拟合现象,即将较多的原始视频序列判定为对抗输入,从而导致∆指标较大. 例如,SiamRPNpp+DF跟踪器在LaSOT*数据集上的Npre性能与SiamRPNpp跟踪器在LaSOT数据集上的Npre性能差距为0.081.
3.5 检测框架泛化性验证
为了验证检测框架的泛化性,本节将检测框架直接集成到其他跟踪器,如SiamMask[30],SiamRPN[31],SiamCAR[32],SiamBAN[33],用于检测TTP攻击. 整个过程无需优化检测框架. 表5展示了检测框架集成到不同跟踪器上时,在混合数据集OTB2015*上的检测性能. 可以看出,提出的检测框架能够协助多个跟踪器实现有效的对抗检测. 例如,检测框架集成到SiamRPN和SiamBAN上,能够协助这2个跟踪器在OTB2015*数据集上分别取得97.67%的召回率和100%的检测精度. 提出的检测框架是以全频和低频段跟踪性能的差异性为判别基础,所以不受限于跟踪器结构,具有较好的检测泛化性. 此外,检测框架对这些跟踪器的原始性能影响也较小,如图7所示. 例如,SiamMask跟踪器在OTB2015数据集上能够取得0.647的AUC,而SiamMask+DF跟踪器在OTB2015*数据集上能够取得0.646的AUC,仅相差0.001.
表 5 检测框架在其他跟踪器上的检测性能 %Table 5. Detection Performance of Detection Framework Integrated into Other Trackers评估指标 SiamRPN SiamMask SiamCAR SiamBAN P 93.33 92.68 100 100 R 97.67 90.48 87.50 93.62 F1 95.45 91.57 93.33 96.70 3.6 判别阈值选择实验
在判别模块中,区间条件是为了减少因跟踪器性能不足和攻击效果有限所带来的判别误差;机理条件则反映了攻击前后不同频段分量上跟踪性能的差异上限. 为了验证所设判别阈值的合理性,本节使用SiamRPNpp+DF跟踪器,分别在由CSA构造的混合数据集OTB2015*,由TTP构造的混合数据集UAV123*,以及由Spark构造的混合数据集LaSOT*上执行跟踪任务,通过改变 a1 , a2 , a3 , a4 的方式,选定最优的阈值组合. 图8展示了阈值变化对检测性能F1的影响. 可以看出,阈值 a1 和 a2 过大会导致大量的对抗视频序列因无法满足判别条件C1和C2,而被错判为原始输入;阈值过小则会弱化输入视频序列的全频段和低频段跟踪性能之间的差异性,增加判定的不确定性. 阈值 a3 决定了跟踪器成功跟踪的下限,所以 a3 过小意味着跟踪器的跟踪性能短板被放大,导致许多原始视频序列被错判为对抗输入. 阈值 a4 决定了跟踪器跟踪失败的上限,所以 a4 过大意味着攻击方法的有效性被放大,使得更多对抗视频序列参与C1和C2条件判别.
3.7 消融实验
3.7.1 判别条件分析
为了分析各个判别条件对检测性能的影响,本节以SiamRPNpp+DF跟踪器在由CSA构造的UAV123*混合数据集上执行跟踪任务为例,对比了不同判别条件下的检测结果. 消融结果如表6所示:
表 6 判别条件对检测性能的影响Table 6. Impact of Discrimination Conditions on Detection Performance% 评估指标 C1 C2 C1+C2 C1+C2+C3 本文条件 P 92.50 94.08 92.66 93.73 95.24 R 47.13 90.24 91.88 94.79 96.99 F1 62.30 92.12 92.27 94.25 96.10 由表6可以看出,随着判别条件逐渐精细化,检测性能越来越好. 相比于条件C1,条件C2下的检测性能更好,反映了CSA对跟踪器置信分数的攻击更加剧烈,故产生了更明显的置信分数差异. 相比于C1+C2条件,本文默认条件下的检测性能更佳,这是因为C3和C4是考虑到跟踪器自身性能不足和攻击方法有效性所设置的区间条件.
3.7.2 低频段范围对检测性能的影响
为了分析频段分量对检测性能的影响,本节以SiamRPNpp+DF跟踪器在由CSA构造的OTB2015*混合数据集上执行跟踪任务为例,以0.1为频段步长逐步扩大镜像跟踪器输入视频序列的频段范围,对比不同频段范围下的检测性能,如图9所示. 可以看出,随着频段范围扩大,检测精度P的变化较小,而召回率R变化较大. 这是因为频段范围的扩大意味着镜像跟踪器的输入包含了更广范围的频段分量,其输入与目标跟踪器的输入差距在不断地缩小. 2个跟踪器的输入差距变小,自然导致二者输出结果的差异性也变小,即弱化了跟踪性能差异性.
3.8 可视化结果展示
本节以SiamRPNpp跟踪器为例,展示其受CSA攻击前后的跟踪结果可视化图及其频谱图. 如图10和图11所示,其中第1行的虚线边框表示待跟踪的真实目标. 通过对比2图的第1行可以看出,原始图像和对抗图像的视觉差异较小. 通过对比2图第2行的跟踪结果可视化图可以看出,受CSA攻击前,可视化图具有大面积的高热区域,说明跟踪器此刻能够以高置信度准确地定位到目标区域. 相反,受CSA攻击后,可视化图上的高热区域消失或变小,说明跟踪器此刻难以准确地定位目标位置,表明跟踪器的性能变差. 图10和图11的第3行分别表示原始图像和对抗图像的频谱图,其中频谱图的左上角区域表示低频段区域,其余区域可以视为中高频段区域. 通过对比可以看出,攻击前后频谱图的低频段区域(左上角区域)差异不大. 然而攻击后,对抗图像频谱图的中高频段区域(椭圆)出现了较多的“亮斑”,证明了添加的扰动噪声主要存在于图像的中高频段.
4. 总结与展望
根据扰动噪声不可见但能有效攻击的特点,首先理论证明了扰动噪声主要存在于视频序列的中高频段;然后定量地分析出低频段分量对跟踪性能的贡献最大且受扰动噪声的影响最小;最后提出了适用于跟踪模型的对抗检测框架,该框架以跟踪器为载体,仅包含频域分解模块,镜像跟踪器以及判别模块. 通过对比视频序列不同频段分量的跟踪性能差异性,即可判定输入视频序列是否受到对抗攻击. 为了验证检测框架的有效性,将其集成到多个跟踪器,用于检测主流的对抗攻击. 大量的实验结果表明所提的检测框架具有泛化性,不仅能够有效地检测多种对抗攻击,而且对跟踪器的原始跟踪性能影响较小. 未来将提取更具判别性的特征,摆脱当前方法对标签信息的依赖,实现在线对抗检测;同时重点研究如何去除扰动噪声,提高跟踪模型抵御对抗攻击的鲁棒性.
作者贡献声明:周泽提出了方法思路和撰写论文;孙颖慧协助完成实验和数据整理;孙权森负责实验监督和领导;沈肖波和郑钰辉提出指导意见并修改论文.
-
表 1 TriBA架构下的路由解决方案
Table 1 Routing Solutions Schemes for TriBA Architecture
算法 对比方法 延迟
( \downarrow )吞吐量
( \uparrow )功耗
( \downarrow )路由级
死锁协议级
死锁Look-up Table[11] 2D-Mesh √ √ × √ × DDRA[35] × × Min-DDRA[36] DDRA √ × × DM4T[27] DDRA √ √ × √ × SPORT[37] DDRA和
Min-DDRA√ × × SPR4T[3] SPORT √ √ × × LA4T[38] DDRA和SPORT √ √ √ × √ HamSPR(本文) SPR4T和LA4T √ √ √ √ √ 注: \downarrow 表示降低; \uparrow 表示提升;√ 表示满足;× 表示不满足. 表 2 SE模式和FS模式下的仿真参数
Table 2 Simulation Parameters in SE and FS Modes
模式 参数 数值 SE 节点数 27 仿真和预热/周期 40000 ,1000 虚拟网络和通道 3,4 路由器延迟/周期 4 线路延迟/周期 1 死锁阈值/周期 150 缓存一致性协议 Garnet Standalone 数据包交换 Wormhole Flit大小/b 128 SA分配策略 Round-Robin CPU频率/GHz 1.0 FS ISA x86 系统内核 x86-Linux-kernel-4.19.83 CPU类型 x86KVMCPU,2.0 GHz L1 cache Private, 16 KB, 2-way associative,
64 B block sizeL2 cache Shared, 2 MB, 8-way associative,
64 B block size内存类型 SimpleMemory,3 GB 缓存一致性协议 MESI Two Level 基准测试集规模 simsmall 表 3 HamSPR在不同网络规模下相比其他算法的性能差异
Table 3 Performance Variation of HamSPR Compared with Other Algorithms for Different Network Scales
网络规模 平均数据包延迟降低/% 吞吐量提升/% Table SPR4T LA4T Table SPR4T LA4T 9 46.67 43.84 40.75 27.29 26.29 21.21 27 48.28 45.78 39.46 27.35 27.35 19.69 81 45.35 43.94 37.64 25.86 26.56 18.74 243 45.95 42.98 37.17 26.08 26.44 19.22 方差 1.2053 1.0422 2.0631 0.4662 0.1691 0.8597 -
[1] Yazdanpanah F, Afsharmazayejani R. A systematic analysis of power saving techniques for wireless network-on-chip architectures[J]. Journal of Systems Architecture, 2022, 126: 102485 doi: 10.1016/j.sysarc.2022.102485
[2] Della Vecchia G, Sanges C. A recursively scalable network VLSI implementation[J]. Future Generation Computer Systems, 1988, 4(3): 235−243 doi: 10.1016/0167-739X(88)90007-6
[3] 石峰,陈旭,尹飞,等. 基于 S3 变换的 TriBA-Net 最短路径路由机制[J]. 中国科学:信息科学,2018,48(1):100−114 doi: 10.1360/N112017-00065 Shi Feng, Chen Xu, Yin Fei, et al. A shortest path routing mechanism based on S3 for TriBA-Net[J]. SCIENTIA SINICA Informationis, 2018, 48(1): 100−114 (in Chinese) doi: 10.1360/N112017-00065
[4] 张洋,王达,叶笑春,等. 众核处理器片上网络的层次化全局自适应路由机制[J]. 计算机研究与发展,2016,53(6):1211−1220 doi: 10.7544/issn1000-1239.2016.20150149 Zhang Yang, Wang Da, Ye Xiaochun, et al. A global hierarchical adaptive routing mechanism in many-core processor network-on-chip[J]. Journal of Computer Research and Development, 2016, 53(6): 1211−1220 (in Chinese) doi: 10.7544/issn1000-1239.2016.20150149
[5] Feng Yinxiao, Xiang Dong, Ma Kaisheng. Heterogeneous die-to-die interfaces: Enabling more flexible chiplet interconnection systems[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 930−943
[6] Bakhouya M, Suboh S, Gaber J, et al. Analytical performance comparison of 2D mesh, wk-recursive, and spidergon nocs [C/OL]//Proc of the 19th IEEE Int Symp on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). Piscataway, NJ: IEEE, 2010[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/5470784
[7] 石峰,魏增辉,王一拙,等. 一种多/众核架构TriBA-CMPs的布局布线方案tMesh:中国,CN107526894A[P]. 2017-12-29 Shi Feng, Wei Zenghui, Wang Yizhuo, et al. A layout and routing scheme named tMesh for a multi/many-core architecture TriBA-CMPs: China, CN107526894A[P]. 2017-12-29 (in Chinese)
[8] Braham C C, Ji Weixinga, Zhang Lingyu. The design and implementation of a hierarchical network on chip[J]. Procedia Engineering, 2012, 29: 2966−2974
[9] Feng Shi, Yang Zhang. Design and evaluation of low-latency and shortest-path routing algorithm for triplet-based hierarchical interconnection network[J]. Journal of Testing and Evaluation, 2013, 41(4): 541−550 doi: 10.1520/JTE20120212
[10] Khan HUR, Shi Feng, Ji Weixing, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29): 3363−3371 doi: 10.1007/s11434-010-4118-z
[11] Wang Zuo, Zuo Qi, Li Jiaxin. Triplet-based topology for on-chip networks[J]. WSEAS Transactions on Computers, 2009, 8(3): 516−525
[12] Xue Licheng, Shi Feng, Ji Weixing. 3D floorplanning of low-power and area-efficient network-on-chip architecture[J]. Microprocessors and Microsystems, 2011, 35(5): 484−495 doi: 10.1016/j.micpro.2011.04.001
[13] Zhang Yang, Shi Feng, Zuo Qi, et al. Express router microarchitecture for triplet-based hierarchical interconnection network[C]//Proc of the 14th IEEE Int Conf on High Performance Computing and Communication & 9th IEEE Int Conf on Embedded Software and Systems. Piscataway, NJ: IEEE, 2012: 295−302
[14] Wang Xiaojun, Shi Feng, Zhang Hong. KLSAT: An application mapping algorithm based on Kernighan–Lin partition and simulated annealing for a specific WK-recursive NoC architecture[C]//Proc of the 16th IFIP WG 10.3 Int Conf on Network and Parallel Computing. Berlin: Springer, 2019: 31−42
[15] Zhang Hong, Wang Xiaojun. KGT: An application mapping algorithm based on Kernighan–Lin partition and genetic algorithm for WK-recursive NoC architecture[C]//Proc of the 17th Int Conf on Intelligent Computing Theories and Application (ICIC). Berlin: Springer, 2021: 86−101
[16] Shi Feng, Li Jiaxin, Bai Ziru. Performance of triplet-based interconnection strategy for multi-core on-chip processors[C]//Proc of the 11th IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2009: 163−170
[17] Wang Xiaojun, Shi Feng, Zhang Hong. A novel speedup evaluation for multicore architecture based topology of on-chip memory[C]//Proc of the 10th Int Symp on Parallel Architectures, Algorithms and Programming. Berlin: Springer, 2019: 35−47
[18] Feng Yinxiao, Xiang Dong, Ma Kaishen. A scalable methodology for designing efficient interconnection network of chiplets [C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1059−1071
[19] Kasan H, Kim J. VVQ: Virtualizing virtual channel for cost-efficient protocol deadlock avoidance[C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1072−1084
[20] Romanov A Y, Myachin N M, Lezhnev E V, et al. Ring-Split: Deadlock-free routing algorithm for circulant networks on chip[J]. Micromachines, 2023, 14(1): 141 doi: 10.3390/mi14010141
[21] Kwauk G, Kang S, Kasan H, et al. Boomgate: Deadlock avoidance in non-minimal routing for high-radix networks[C]//Proc of the 2021 IEEE Int Sym on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2021: 696−708
[22] Flich J, Skeie T, Mejia A, et al. A survey and evaluation of topology-agnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(3): 405−425
[23] Wu Yibo, Wang Liang, Wang Xiaohang, et al. A deflection-based deadlock recovery framework to achieve high throughput for faulty NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(10): 2170−2183
[24] Razavi S, Sarbazi-Azad H. The triangular pyramid: Routing and topological properties[J]. Information Sciences, 2010, 180(11): 2328−2339 doi: 10.1016/j.ins.2010.02.016
[25] Wang Nengchung, Yen Chengpang, Chu Chihping. Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model[J]. Journal of Systems Architecture, 2005, 51(3): 165−183 doi: 10.1016/j.sysarc.2004.11.001
[26] El-Obaid A. Three-dimension Hamiltonian broadcast wormhole-routing[J]. International Journal of Computer Networks & Communications, 2015, 7(3): 31−46
[27] Chen Xu, Shi Feng, Yin Fei, et al. An efficient distributed minimal routing algorithm for triplet-based WK-recursive network[C]//Proc of the 20th IEEE Int Conf on High Performance Computing and Communications; 16th IEEE Int Conf on Smart City; 4th IEEE Int Conf on Data Science and Systems (HPCC/SmartCity/DSS). Piscataway, NJ: IEEE, 2018: 547−554
[28] Fan Dongrui, Zhang Hao, Wang Da, et al. Godson-T: An efficient many-core processor exploring thread-level parallelism[J]. IEEE Micro, 2012, 32(2): 38−47 doi: 10.1109/MM.2012.32
[29] Parasar M, Farrokhbakht H, Jerger N E, et al. DRAIN: Deadlock removal for arbitrary irregular networks[C]//Proc of the 2020 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2020: 447−460
[30] Dally W J, Towles B P. Principles and Practices of Interconnection Networks[M]. Amsterdam: Elsevier, 2004
[31] Ramey C. Tile-GX100 manycore processor: Acceleration interfaces and architecture[C/OL]//Proc of the 23rd IEEE on Hot Chips Symp. Piscataway, NJ: IEEE, 2011[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/7477491
[32] Wentzlaff D, Griffin P, Hoffmann H, et al. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15−31 doi: 10.1109/MM.2007.4378780
[33] Sodani A, Gramunt R, Corbal J, et al. Knights landing: Second-generation intel Xeon Phi product[J]. IEEE Micro, 2016, 36(2): 34−46 doi: 10.1109/MM.2016.25
[34] Rahman R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers[M]. Berlin: Springer, 2013
[35] Qiao Baojun, Shi Feng, Ji Weixing. A new hierarchical interconnection network for multi-core processor[C]//Proc of the 2nd IEEE Conf on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2007: 246−250
[36] Wang Zuo, Shi Feng. A shortest path routing algorithm in triplet-based network[J]. Transactions of Beijing Institute of Technology, 2009, 29(5): 410−414
[37] Zhang Yang, Shi Feng, Ji Weixing, et al. SPORT: A shortest path routing algorithm for triplet-based hierarchical interconnection[J]. Transactions of Beijing institute of Technology, 2013, 33(1): 57−61
[38] Chen Xu, Shi Feng, Yin Fei, et al. A novel look-ahead routing algorithm based on graph theory for triplet-based network-on-chip router[J]. IEICE Electronics Express, 2018, 15(8): 1−12
[39] 石峰,阮生强,尹飞,等. 基于尖端子图分类传输数据的基三核间网络防死锁方法:中国,CN112698960B[P]. 2022-08-09 Shi Feng, Ruan Shenqiang, Yin Fei, et al. A deadlock prevention method for inter-core networks based on apex-subgraph classification for data transmission in triplet-based architecture: China, CN112698960B[P]. 2022-08-09 (in Chinese)
[40] Tutte W T. Graph Theory[M]. Cambridge, UK: Cambridge University Press, 2001
[41] Levine G N. The classification of deadlock prevention and avoidance is erroneous[J]. ACM SIGOPS Operating Systems Review, 2005, 39(2): 47−50 doi: 10.1145/1055218.1055221
[42] Binkert N, Beckmann B, Black G, et al. The GEM5 simulator[J]. ACM SIGARCH Computer Architecture News, 2011, 39(2): 1−7 doi: 10.1145/2024716.2024718
[43] Bharadwaj S, Yin J, Beckmann B, et al. Kite: A family of heterogeneous interposer topologies enabled via accurate interconnect modeling[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2020[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/9218539
[44] Sun Cheng, Chen C H O, Kurian G, et al. DSENT―A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling[C]//Proc of the 6th IEEE/ACM Int Symp on Networks-on-Chip. Piscataway, NJ: IEEE, 2012: 201−210
[45] Zhan Xusheng, Bao Yungang, Bienia C, et al. PARSEC3.0: A multicore benchmark suite with network stacks and SPLASH-2X[J]. ACM SIGARCH Computer Architecture News, 2017, 44(5): 1−16
[46] Parasar M, Jerger N E, Gratz P V, et al. SWAP: Synchronized weaving of adjacent packets for network deadlock resolution[C]//Proc of the 52nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2019: 873−885
[47] Joshi B, Thakur M K. Genetic algorithm-and cuckoo search algorithm-based routing optimizations in network-on-chip[J]. Arabian Journal for Science and Engineering, 2023, 48(8): 9635−9644 doi: 10.1007/s13369-022-07272-9
[48] Luo Yaoying, Meyer M C, Jiang Xin, et al. A hotspot-pattern-aware routing algorithm for networks-on-chip[C]//Proc of the 13th IEEE Int Symp on Embedded Multicore/Many-core Systems-on-Chip (MCSoC). Piscataway, NJ: IEEE, 2019: 229−235