具有温度感知特性的实时调度研究

处理器温度的上升严重危害着处理器的性能。DTM（Dynamic Thermal Management）是一种硬件层面的热管理机制,它会带来一定的性能损失。提出了一种操作系统层面的针对实时任务的动态热管理机制——LTEDF（Low Thermal Early Deadline First）。LTEDF通过在线实时获取性能计数器的值,计算处理器当前温度来动态调度队列中的线程,提出了MST（Maximum Scheduling Threshold）启发式方法。基于HotSpot温度模型对算法进行了仿真实验,结果显示,该算法不仅可以满足任务的时间限制而且可以满足温度限制,并且较传统的EDF（Early Deadline First）LTEDF算法可以创建更加统一的功率密度图,MST启发式算法可以明显减少线程迁移带来的开销。     

基于异构感知静态调度与动态迁移的异构多核调度机制

异构多核处理器体系结构可以有效减少功效开销,是处理器发展的趋势,负载不平衡问题会造成处理器执行的不稳定。提出一种基于异构感知的静态调度和动态线程迁移相结合的异构多核调度机制,解决了不同核之间的负载平衡问题,提高了吞吐量。仿真实验通过将此调度机制与静态调度策略（SS）比较,表明该机制提高了异构多核处理器的性能并保证了执行过程的稳定性。     

一种异构多核处理器启发式综合任务调度算法

针对现有异构多核处理器(CMP)任务调度算法中存在的优先级排序机制不健全、任务调度效率不高的问题,提出一种基于启发式的综合任务调度算法。该算法以表调度为基础,面向平台异构性和依赖任务特性,给出一种按照加权优先级构造任务调度列表的方式。在此基础上,采用多任务复制技术减少核间依赖任务的通信时延,提早任务的最早开始时间,并在任务分配阶段采取区间插入的方式将任务分配到合适的处理器内核上执行,以提高处理器资源利用率。设计模拟实验对该算法性能和已有的2个较为高效的启发式任务调度算法进行对比实验,结果证明该算法能有效提升任务调度性能。     

混合粒子群算法的异构多核处理器间任务调度

针对异构多核处理器间的任务调度问题,为了更好地发挥异构多核处理器间的平台优势,提出一种基于将有关联的且不在同一处理器上的任务进行复制的思想,从而使每个异构多核的处理器能独立执行任务,来减少不同处理器之间的通信开销,并且通过混合粒子群算法(HPSO)来调度异构多核处理器中的任务,避免由于当任意一个异构多核处理器由于任务分配过多而导致计算机不能及时且准确地得出结果.最后实验证明,对比传统的启发式分配方案和常见的遗传算法(GA),基于任务复制思想分配方案和混合粒子群算法(HPSO)具有更好的求解能力,并且可以提供执行时间更少的调度分配方案,具有较好的应用价值.     

基于任务图的并行调度MEWFM算法

随着多核处理器体系结构在计算机领域的广泛应用,如何合理地对计算任务进行调度成为人们广泛讨论的问题。目前已经有针对多处理器的任务调度算法,但是这些算法在执行时要经过多次迭代,执行效率比较低。提出一种改进的波前调度算法MEWFM,它是一种执行时间短,加速比接近处理器核数的一种算法。这种算法主要包括任务图分层,层内调度和误差下降调度三个子算法。详细分析了这些算法的特点和执行流程。实验评测表明,算法在多处理器环境下的任务调度方面具有执行速度快,性能高等优势。     

一种面向多核系统的并行计算任务分配方法

随着多核处理器的普及,目前的大规模并行处理系统普遍采用多核处理器,这对于资源管理和调度提出了更高的要求.提出了基于共享Cache资源划分的方法,建立了面向多核处理器支持Cache资源分配的进程调度模型,设计并实现了并行任务到多核处理器的映射算法,更好地解决了大规模资源管理系统中面向多核处理器的任务分配问题,降低了使用共享Cache的多个进程运行时的相互干扰,提升了应用程序性能.     

面向动态异构多核处理器的公平调度算法

动态异构多核处理器的处理器核可动态调整的特征给操作系统调度算法带来了新的机遇和挑战.利用处理器核动态可调整的特征能更好地适应不同任务的运行需求,带来巨大的性能优化空间.然而也带来新的代价和更复杂的公平性的计算.为了解决面向动态异构多核处理器结构上的公平性调度问题,提出了一个基于集中式运行队列的调度模型,以降低调度算法在动态处理器核变化所带来的维护开销.并重新思考在动态异构处理器结构下公平性的定义,基于原有CFS调度算法提出新的HFS调度算法.HFS调度算法不仅能简单而有效地利用动态异构多核处理器的性能优势,而且能提供在动态异构多核处理器上的公平性调度.通过模拟SCMP,ACMP,DHCMP平台,证明了提出的HFS调度算法能够很好地发挥DHCMP结构的性能特征,比运行目前主流调度算法的SCMP和ACMP结构提升10.55%的用户级性能(ANTT),14.24%的系统吞吐率(WSU).     

基于多核处理器的关联任务并行感知调度算法

关联任务在多核处理器上并行调度所产生的通信时延,会对任务调度长度和处理器利用率造成负面影响,为了改善多核系统对关联任务的处理性能,针对关联任务在多核处理器上的调度特点,提出一种并行感知调度算法。计算各任务与终点间的最长路径值,按照该值的降序来分配任务调度次序,在分配处理器内核时兼顾关联度和任务最早可执行时间,设置最佳匹配评价函数。实验结果表明,与busHEFT和DTSV算法相比,该算法具有更短的任务调度时延、更少的通信量以及更高的处理器利用率。     

基于遗传蚁群算法的CMP线程调度方法

为提高多核处理器系统的调度效率,充分发挥多核处理器的性能,提出了一种新的线程调度算法。该方法利用遗传算法的快速随机全局搜索能力,生成蚁群算法所需的信息素分布,利用蚁群算法的正反馈性,并将其应用到CMP的线程调度中,以提高线程调度的效率。通过两种算法的结合,弥补了遗传算法随着求解范围增大而效率降低,蚁群算法需要信息素浓度的增加才能提高效率的不足,更好地发挥它们的优势,提升求解速度。实验结果表明,该算法能够很好地降低任务的执行时间,充分发挥多核处理器系统的优势。     

分布式系统下的启发式任务调度算法

为了提升异构分布式环境下处理具有依赖关系的任务的性能,提出一种基于关键任务和处理器选择参数的启发式任务调度算法（HCNPSV）。该算法结合表调度和任务复制调度的思想,改进了关键任务的计算方法,并按照是否为关键任务、上行权重值递减、关联任务数递增的顺序获得调度序列,资源选择阶段综合考虑了任务的最早完成时间和到出口节点的最短距离,最后将任务调度到处理器选择参数最小的资源上执行。实验结果表明,HCNPSV有效地提高了系统的调度性能。     

基于用户延迟感知的移动边缘服务器放置方法

物联网和5G网络的快速发展产生了大量数据,通过将计算任务从移动设备卸载到具有足够计算资源的边缘服务器上,可有效减少网络拥塞和数据传播延迟等问题。边缘服务器放置是任务卸载的核心,高效的边缘服务器放置方法能有效满足移动用户访问低时延、高带宽等需求。为此,文中以最小化访问延迟和最小化负载差异为优化目标,建立边缘服务器放置优化模型;然后,提出了一种基于改进启发式算法的移动边缘服务器放置方法ESPHA(Edge Server Placement Based on Heuristic Algorithm),实现多目标优化。首先将K-means算法与蚁群算法相结合,通过效仿蚁群在觅食过程中共享信息素,将信息素反馈机制引入边缘服务器放置方法中,然后,通过设置禁忌表对蚁群算法进行改进,提高算法的收敛速度;最后,用改进的启发式算法求解模型的最优放置方案。使用上海电信真实数据集进行实验,结果表明提出的ESPHA方法在保证服务质量的前提下取得了低延迟和负载均衡之间的优化平衡,其效果优于现有的其他几种代表性的方法。     

A hybrid genetic algorithm for feature subset selection in rough set theory

Rough set theory has been proven to be an effective tool to feature subset selection. Current research usually employ hill-climbing as search strategy to select feature subset. However, they are inadequate to find the optimal feature subset since no heuristic can guarantee optimality. Due to this, many researchers study stochastic methods. Since previous works of combination of genetic algorithm and rough set theory do not show competitive performance compared with some other stochastic methods, we propose a hybrid genetic algorithm for feature subset selection in this paper, called HGARSTAR. Different from previous works, HGARSTAR embeds a novel local search operation based on rough set theory to fine-tune the search. This aims to enhance GA’s intensification ability. Moreover, all candidates (i.e. feature subsets) generated in evolutionary process are enforced to include core features to accelerate convergence. To verify the proposed algorithm, experiments are performed on some standard UCI datasets. Experimental results demonstrate the efficiency of our algorithm.     

一种新的用于连续值属性离散化的约简算法

针对在Nguyen和Skowron的离散化算法中进行启发式约简时会出现某些属性不能进行离散化问题，以及在无核数据集中启发式约简算法计算量比较大等问题，在粗糙集理论和属性频率函数的基础上给出一个新概念－候选核，并提出一种新的用于连续值属性离散化的约简算法－基于候选核的启发式约简算法（简称BCC）。该算法可以寻找到能对所有属性进行离散化的约简，实验表明，所提出的BCC算法能提高大数据集的离散化效果。     

指令级密码处理器软件功耗建模与仿真

为了分析密码处理器软件的功耗,提高软件的抗能量攻击能力,提出了基于指令的处理器功耗建模仿真方法;详细阐述了模型建立、指令功耗求解算法以及指令功耗采集平台建立方法;在此基础上对一款密码专用处理器的AES加密算法软件功耗进行了仿真,对仿真结果和实际测量结果进行了比较分析,结果表明这种处理器功耗建模方法是有效的。     

Improving Adaptability and Per-Core Performance of Many-Core Processors Through Reconfiguration

Increasing the number of cores in a multi-core processor can only be achieved by reducing the resources available in each core, and hence sacrificing the per-core performance. Furthermore, having a large number of homogeneous cores may not be effective for all the applications. For instance, threads with high instruction level parallelism will under-perform considerably in the resource-constrained cores. In this paper, we propose a core architecture that can be adapted to improve a single thread’s performance or to execute multiple threads. In particular, we integrate Reconfigurable Hardware Unit (RHU) in the resource-constrained cores of a many-core processor. The RHU can be reconfigured to execute the frequently encountered instructions from a thread in order to increase the core’s overall execution bandwidth, thus improving its performance. On the other hand, if the core’s resources are sufficient for a thread, then the RHU can be configured to executed instructions from a different thread to increase the thread level parallelism. The RHU has low area overhead, and hence has minimal impact on scalability of the number of cores. To further limit the area overhead of this mechanism, generation of the reconfiguration bits for the RHUs of multiple cores is delegated to a single core. In this paper, we present the results for using the RHU to improve a single thread’s performance. Our experiments show that the proposed architecture improves the per-core performance by an average of about 23% across a wide range of applications.     

Animal migration optimization: an optimization algorithm inspired by animal migration behavior

In this paper, we intend to propose a new heuristic optimization method, called animal migration optimization algorithm. This algorithm is inspired by the animal migration behavior, which is a ubiquitous phenomenon that can be found in all major animal groups, such as birds, mammals, fish, reptiles, amphibians, insects, and crustaceans. In our algorithm, there are mainly two processes. In the first process, the algorithm simulates how the groups of animals move from the current position to the new position. During this process, each individual should obey three main rules. In the latter process, the algorithm simulates how some animals leave the group and some join the group during the migration. In order to verify the performance of our approach, 23 benchmark functions are employed. The proposed method has been compared with other well-known heuristic search methods. Experimental results indicate that the proposed algorithm performs better than or at least comparable with state-of-the-art approaches from literature when considering the quality of the solution obtained.     

Intrusive tumor growth inspired optimization algorithm for data clustering

Inspired by the invasive tumor growth mechanism, this paper proposes a new meta-heuristic algorithm. A population of tumor cells can be divided into three subpopulations as proliferative cells, quiescent cells, and dying cells according to the nutrient concentration they get. Different cells have different behaviors and interactions among them for competition. In the tumor growing process, an invasive cell is born around a proliferative cell for the higher nutrient concentration and a necrotic cell occurs around a dying cell for the lower nutrient concentration, which presents the balance between life and death. To evaluate the performance of the intrusive tumor growth optimization algorithm (ITGO), we compared it to the many well-known heuristic algorithms by the Wilcoxon’s signed-rank test with Bonferroni–Holm correction method and the Friedman’s test. At the end, it is applied to solve the data clustering problem, which is a NP-hard problem. The experimental results show that the proposed ITGO algorithm outperforms other traditional heuristic algorithms for several benchmark datasets.     

Temperature-aware task scheduling algorithm for soft real-time multi-core systems

High temperature will affect the stability and performance of multi-core processors. A temperature-aware scheduling algorithm for soft real-time multi-core systems is proposed in this paper, namely LTCEDF (Low Thermal Contribution Early Deadline First). According to the core temperature and thread thermal contribution, LTCEDF performs thread migration and exchange to avoid thermal saturation and to keep temperature equilibrium among all the cores. The core temperature calculation method and the thread thermal contribution prediction method are presented. LTCEDF is simulated on ATMI simulator platform. Simulation results show that LTCEDF can not only minimize the thermal penalty, but also meet real-time guarantee. Moreover, it can create a more uniform power density map than other thermal-aware algorithms, and significantly reduce thread migration frequency.     

低能耗软件设计中的性能无损电压调度技术研究

合理地运用动态电压调整技术可以有效降低软件运行所需的能耗·从归纳分析电压调整特征入手,针对程序执行中存在电压调整特征差异的情况,提出了性能无损的低能耗电压调度问题·把该问题形式化为一个混合整数规划模型(MILP),提出了基于剖析结果的PGS算法和基于分析结果的ADS算法·实例分析表明所提出的方法能够有效实现性能无损的低能耗软件设计,模拟实验表明启发式算法可实现较好的近似解·