NoC处理单元随机舍入的启发式应用映射

在性能约束的前提下,为了降低能量消耗,针对一个集成了异构IP块以分层星型拓扑互连的片上网络(NoC),采用多电压电平操作,运用一种统一方法来解决应用映射问题,并用混合整数线性程序公式化问题,提出了基于随机舍入的NoC处理单元启发式高效应用映射——HAMU法.实验结果表明,HAMU法的效能明显优于其他启发式方法.

用户公平保障的边缘服务缓存与任务卸载算法

在边缘服务器中缓存服务可缩短请求响应时间,提升用户体验。现有研究主要从整体上优化系统性能,例如最大化系统吞吐量,而无法保障个体用户请求异构服务的公平性。针对用户异构计算任务的不公平服务问题,研究边缘协同计算中的服务缓存和任务卸载策略,基于最大最小公平原则,构建了一个最大化最小服务完成率问题,并证明了其NP难解性。为此,利用线性松弛将原问题从0-1整数规划转化为线性规划,设计了一种近似比为M S/N(S-2 ln S)的随机舍入算法,其中S为边缘服务器数,N为服务数,M为终端设备数。同时,基于优先缓存和卸载完成率最小的服务及其任务,提出了一种快速高效的贪心算法。实验结果表明,与已有最大化系统吞吐量算法相比,提出的随机舍入算法和贪心算法将最小服务完成率分别提升至少44.1%和90.6%,并且其额外的系统吞吐量损失分别不超过22.4%和27.0%。

带有顶点权重约束的图划分问题研究

研究了带有顶点权重约束的图划分问题.首先基于矩阵的提升将原问题转化为半定规划松弛模型,利用半定规划内点法求解该模型,并在求解过程中给出了具体的初始点选取策略和步长选取策略.随后利用改进的随机超平面舍入算法和2opt启发式算法求得原问题的近似最优解.数值实验表明该文的算法可有效求解带有顶点权重约束的图划分问题,且对于稀疏图的求解表现出了良好的性能.

限制设施选址问题的近似算法

提出了设施选址问题的一个新变体—限制设施选址问题,给出了一个基于随机线性规划舍入的近似算法,并分析了算法的近似度。