多选择软硬件划分问题的计算模型与动态规划算法

软硬件划分是软硬件协同设计的关键环节,划分的结果直接影响目标系统的设计质量。因此,对于一个给定的应用程序,为了使得目标系统快速执行且成本低廉,合理的划分策略十分重要。由于单个任务具有多种不同的硬件实现方式,与传统的单一硬件实现方式的软硬件划分问题相比,多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性,它们已被证明是NP完全问题。基于多核处理器片上系统并针对任务图为二叉树的应用,建立了多选择软硬件划分问题的计算模型,并提出了解决该问题的动态规划算法。实验结果表明,当问题规模适中时,所提动态规划算法能够有效地获得精确解,并展示了算法的计算能力与硬件面积限制之间的关系。     

树形网络中的副本更新策略及算法

树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一。面对网络中数据访问需求的动态变化,好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本。针对此问题提出了两种贪心的动态副本更新策略,最大重用策略和请求覆盖策略。通过算法复杂度分析和仿真实验可以看出,所提出的两种算法的最坏时间复杂度为O(nlog n),远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5),而网络运行及副本更新成本与最优解相差不超过11%。在极大地缩短了运算时间的同时,保持了尽可能低的网络运行及副本更新成本。     

容错处理器阵列的多逻辑列并行重构算法

处理器阵列的容错重构技术是片上网络多核、众核高性能体系结构的可靠性技术之一。现有的最大逻辑阵列并行重构技术仅对单条逻辑列的构造实现了并行化,而对多条逻辑列的同步并行仍未见可行算法。依据处理器阵列的潜在并行性,在分治策略的基础上,提出了一种阵列分块的并行重构算法。算法对处理器阵列实施横向分块划分,对每个阵列块进行并行重构,并对所得逻辑子阵列进行归并,实现了多条逻辑列的同步并行重构。与现有的并行算法相比,新算法同样能够生成最大逻辑列,并且减少了通信开销与计算中的数据冗余,有效提高了运行速度。实验结果表明,在物理阵列大小为64×64的处理器阵列上,运行速度比现有并行算法提高39.55%,并且具有良好的可扩展性。     

基于海量公交轨迹数据挖掘的地图匹配算法

针对现有地图匹配算法（如基于经典隐马尔可夫及其变体、先进算法等）对于低频轨迹数据匹配效果不甚理想的问题,提出一种基于海量公交历史轨迹数据的轨迹数据挖掘方法。首先,以公交站点为序列骨架,从大量低频轨迹中挖掘、提取轨迹点数据,进行重组、排序形成高质量高频轨迹数据序列;然后,将高质量高频轨迹数据序列应用基于经典隐马尔可夫模型地图匹配算法,得到公交路线地图匹配结果。与未经过挖掘算法处理的低频轨迹数据的匹配方法相比,所提方法在匹配误差上平均下降6.3%,匹配所需的数据规模、时间大幅缩减;且该方法对于低频、不稳定的噪声数据具有鲁棒性,适用于所有公交路线的地图匹配问题。     

C程序映射到FPGA的寄存器快速评估技术

在基于FPGA的软硬件协同设计中,对硬件面积和延迟时间进行快速准确地评估是快速生成片上异构多处理器系统的关键步骤.使用传统的逻辑综合工具将会耗费大量的时间才能获得面积-时间的度量值,导致在软硬件协同设计流程中,抑制了设计空间的有效探索.本文关注将C程序映射到FPGA,对寄存器数量进行快速和准确的评估.提出的技术以高级综合工具Leg Up和底层虚拟机LLVM为基础,利用信号位宽优化信息、特殊指令信息以及编码方式对寄存器进行评估.实验结果表明,该技术能够对CHStone基准测试程序进行寄存器数量的评估;以Altera CycloneⅡ和StratixⅣFPGA为平台,实验结果的误差分别只有13.75%和10.48%,与使用Quartus工具的逻辑综合运行时间相比,能够实现84倍的加速.     

PRDT（2，1）架构的NoC系统容错路由算法

链路和节点的故障会导致网络中许多节点无法相互通讯,因此容错性是NoC系统设计中的一个重要问题。基于一种新的NoC网络拓扑结构PRDT（2,1）,提出一种PRDT（2,1）容错路由算法以及相应的节点失效算法。节点失效算法通过使较少数量的无故障节点失效来构造矩形故障区域,PRDT（2,1）容错路由算法仅使用了最小数量的虚拟通道并提供足够的自适应性以实现无死锁容错路由。只要故障区域没有断开网络,这一算法能够保证路由的连通性。算法在不同故障率的PRDT（2,1）网络中仿真,结果显示这一算法具有良好的平滑降级使用特性。     

基于二维MB-LBP特征的人脸识别

提出了一种基于二维多尺度局部二进制模式的人脸识别方法,对一幅人脸图像进行分块,对每一块的图像进行MB-LBP（Multi-scale Block Local Binary Patterns）算子运算,将MB-LBP与灰度共现矩阵结合起来得到了可以更好地描述局部纹理空间结构的二维MB-LBP特征,将各子块的二维MB-LBP特征进行连接形成人脸特征。该算法在ORL和CMU-PIE人脸数据库上进行测试,选择了支持向量机（SVM）作为分类器,并与传统的基于一维LBP特征进行比较,结果表明提出的算法在人脸识别问题上的有效性和优越性。     

软硬件协同设计复杂问题的计算模型和算法

软硬件划分是设计复杂嵌入式系统的关键环节.论文综述了近年来提出的解决软硬件划分问题的计算模型和相应算法.软硬件划分问题可以建模成各种限定不同约束条件的背包问题模型,同时需要考虑任务块间的通信消耗.背包问题中的子项相当于软硬件划分问题中的任务块.论文针对不同的计算模型,介绍了相应的精确算法和启发式算法.论文最后探讨了若干待研究的潜在问题.     

堆上的数据分布与堆选择算法

本文对堆上的数据分布进行了测定，根据测定结果并利用堆的性质设计出一个堆选择算法，对于ｎ＜２＾１６，算法的平均复杂度以８．９ｎ为上界。