多核系统共享内存资源分配和管理研究

对于共享内存资源的多核系统来说,分配和管理有限的内存资源是一个非常重要且具有挑战性的问题.随着处理器核数的快速增长,不同线程间的访存请求对系统中共享内存的竞争也愈发激烈,由此导致的对系统性能和系统公平性的影响也更加显著.为了缓解这一问题,除了增加可用共享资源外,公平高效地管理和利用共享内存资源至关重要.在各类共享资源中,对系统性能影响最大的是共享Cache和DRAM.文中将这两级共享内存资源的分配和管理研究归结为三个重要方面,包括共享缓存分区、访存请求调度以及地址映射优化,并从优化系统吞吐率和公平性方面分析总结了一系列共享缓存分区策略,从缓解多线程对DRAM的竞争和相互干扰方面分析概括了一系列访存调度算法和地址映射策略.最后对共享内存资源未来的研究和发展做了总结和展望.     

带有线性恶化工件和释放时间的两个代理单机调度问题

研究了带有简单线性恶化工件和释放时间的两个代理单机调度问题. 所有工件在一台机器上加工, 每个代理有各自依赖于自己工件的优化目标. 针对工件释放时间相同与不同两种情况, 研究了有约束的优化模型, 即找到调度最小化一个代理的目标函数而使得另一个代理的目标函数不超过一个给定的上界. 当工件具有相同的释放时间, 我们主要考虑的目标函数有: 总加权完工时间和总加权拖期工件数. 当工件具有不同释放时间, 我们考虑的目标函数有: 最大完工时间、总完工时间以及拖期工件数. 对于每一个问题, 我们分析了问题的计算复杂性. 此外, 对于NP难问题的一些特殊情况本文分析了最优解性质, 基于这些性质给出了最优算法.     

求解车间作业调度问题的混合遗传模拟退火算法

为了克服传统遗传算法解决车间作业调度问题的局限性,结合遗传算法(GA)和模拟退火算法(SA)的优点,提出一种混合遗传模拟退火算法(GASA),以便高效地解决车间作业调度问题.该算法既发挥了遗传算法收敛速度快、模拟退火算法搜索面广的优点,又克服了前者收敛容易早熟而后者收敛速度较慢的问题.在算法的操作细节上,加入自适应调整的遗传操作及最优个体保留策略,以及增加记忆功能的模拟退火操作与收敛准则.从而既防止了算法会陷入局部最优解的问题,又提高了算法的收敛速度及搜索效率.将提出的混合遗传模拟退火算法(GASA)应用于Muth和Thompson基准问题的实验运行,证明了该算法的高效性和有效性.     

并行实时任务调度判定分析

多核处理器凭借着高性能上的优势逐步取代单核处理器.传统实时任务使用串行任务模型,不能充分发挥多核处理的优势,而基于有向无环图的并行实时任务周期内释放多个作业,这些作业同时运行.并行实时任务集的可调度性是研究的重点,针对该模型分析并证明了在某些条件下全局最早截止期优先算法和单调时限算法的可调度性判定,根据分析的结果提出了实时任务集可调度的判定流程,最后采用资源增值分析了两种判定条件的性能.     

一种改进的实时嵌入式系统容错优化方法

容错技术中硬件冗余会产生较高的设计和生产成本.针对该问题,提出一种改进的实时嵌入式系统容错优化方法,基于检查点容错技术综合分析系统故障性能、硬实时任务时间约束和软实时任务的效用函数值.以设计的容错模型为基础,计算系统故障概率保证其在故障最大概率值内,给出硬任务截止时间确定可调度性,并应用改进的禁忌搜索算法获得软任务效用函数最佳值,算法有2种简单的邻节点结构,其禁忌准则遵循邻节点方法禁忌,优化效率明显改善.实验结果表明,该方法可进行故障分析等综合分析,并能迅速获得最大效用函数值.     

LSO改进CGA解决多目标作业车间调度问题

针对传统方法在处理作业车间调度问题时很难将库存容量考虑在内的问题,提出了基于局部搜索算子(LSO)改进交叉遗传算法(CGA)的多目标作业车间调度模型。为了提高所提模型的效率,首先设计一种基于关键路径的交叉遗传算子;然后,设计一种新的局部搜索算子来提高遗传算法的局部搜索能力;最后,基于这两种算子,设计混合遗传算法框架,在考虑调度总完成时间的同时将库存容量作为目标进行优化。所提算法的有效性在FT10、LA01、LA06、LA11、LA21和LA36等基准问题测试中得到验证。仿真结果表明,与较为先进的非劣分层遗传算法(NSGA-II)相比,使用所提算法获得了更好的非支配解,从而更好地解决了多目标作业车间调度问题。     

无线传感器网络中一种基于可靠性的数据收集算法

为实现无线传感器网络数据的低延时、高可靠性收集,将数据收集时涉及到的收集树构建、链路调度与功率分配联合问题定义为一个使数据收集延时最小化的优化问题。将该问题分成2个子问题：低延时数据收集树的构建和针对数据收集树的链路调度与功率分配,并为每个子问题提供一种多项式启发算法。仿真结果表明,与现有数据收集策略相比,该算法的数据收集延时明显降低,且可靠性更高。     

基于改进回溯搜索优化算法的应急资源调度

以连续性消耗应急系统为背景,建立以时间成本和运输成本最小化为目标的多资源多供应点调度模型。针对该模型的特点,对一种具有强全局搜索性的新智能算法——回溯搜索优化算法进行改进,设计变异操作中的变异尺度系数和交叉操作中的交叉概率策略,提高算法的收敛速度和求解精度。运用改进回溯搜索算法进行模型求解,仿真实例表明,改进回溯搜索优化算法在解决应急资源调度问题时拥有良好的性能,全局收敛性与求解精度均优于比较的回溯搜索优化算法、差分进化算法和粒子群算法,能够有效且合理地进行应急资源调度。     

航班着陆调度的多目标优化研究

航班着陆调度问题是多目标优化问题,难以使用最优化方法求解。为了解决这一难题,以减少航班延迟时间和降低飞行延误成本为目标,提出一种整合的启发式方法。该方法使用吱呀轮算法SWO(Squeaky-Wheel Optimization)进行导向式搜索,并利用改进的GA充分扩展SWO的搜索空间,最后通过合理整合GA和SWO,取得求解效率和求解质量的提高。通过实验仿真对比表明该算法能高效求解该问题,满足了实时调度的需求,同时求解质量也优于其他启发式算法,节省了更多降落时间和成本。     

基于位置与连接概率的EDA算法求解PFSP问题

针对置换流水车间调度问题(PFSP)的特点,提出一种基于工件加工位置与连接概率相结合的混合分布估计算法。该算法将工件位置概率与工件的连接概率结合在一起,作为新一代种群的生成概率从而使得进化趋势更加合理化。为了提高局部搜索能力,算法引入了启发式方法提高初始解质量,优化了邻域搜索策略。同时引入了变异操作及限定操作来提高算法全局搜索能力。实验结果表明,该算法在求解置换流水车间调度问题时具有良好的性能。