英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
ImGA: an improved genetic algorithm for partitioned scheduling on heterogeneous multi-core systems
ImGA：一种在异构多核系统上进行分区调度的改进遗传算法
Rabeh Ayari
Imane Hafnaoui
Giovanni Beltrame
Gabriela Nicolescu
Abstract Efficient mapping of tasks onto heterogeneous multi-core systems is very challenging especially in the context of real-time applications. Assigning tasks to cores is an NP-hard problem and solving it requires the use of meta-heuristics. Relevantly, geneticalgorithms have already proven to be one of the most powerful and widely used stochastic tools to solve this problem. Conventional genetic algorithms were initially defined as a general evolutionary algorithm based on blind operators with pseudo-random operations. It is commonly admitted that the use of these operators is quite poor for an efficient exploration of big problems. Likewise, since exhaustive exploration of the solution space is unrealistic, a potent option is often to guide the exploration process by hints, derived by problem structure. This guided exploration prioritizes fitter solutions to be part of next generations and avoids exploring unpromising configurations by transmitting a set of predefined criteria from parents to children. Consequently, genetic operators, such as initial population, crossover, mutation must incorporate specific domain knowledge to intelligently guide the exploration of the design space. In this paper, an improved genetic algorithm (ImGA) is proposed to enhance the conventional implementation of this evolutionary algorithm. In our experiments, we proved that ImGA leads to perceptible increase in the performance of the genetic algorithm and its convergence capabilities.
摘要
将任务有效的映射到异构多核系统上是非常具有挑战性的，特别是在实时应用的背景下。将任务分配给核心是一个NP难题，解决它需要使用启发式算法。对此，遗传算法已经被证明是解决这个问题的最强大和广泛使用的随机工具之一。传统的遗传算法最初被定义为基于具有伪随机运算的盲算子的一般进化算法。人们普遍承认，对于大问题的有效探索而言，使用这些算子非常差。同样，由于求解空间的详尽探索是不现实的，因此有效的选择通常是通过问题结构导出的提示来指导探索过程。这种指导性探索优先将更好的解决方案作为下一代，并通过从父母向子代传送一套预定义标准来避免探索没有希望的方案。因此，遗传操作，如初始种群，交叉，变异必须结合特定的领域知识，以智能地指导设计空间的探索。在本文中，提出了一种改进的遗传算法（ImGA）来增强这种进化算法的传统实现。在我们的实验中，我们证明了ImGA可以显着提高遗传算法的性能及其收敛能力。
Keywords Design methodology · Optimization · Embedded systems · Real-time application·Heterogeneous multi-core architectures·Partitioning·Genetic algorithm
关键词
设计方法 优化 嵌入式系统 实时应用 异构多核结构 分区 遗传算法
1 Introduction
1、简介
The trend in the design of modern hardware platforms has shifted towards increasing the number of processing elements. The rise of multi-core architectures reshaped computer engineering, and long-lasting certainties had to be updated. Moorersquo;s law shifted its focus from the number of transistors to the number of cores that could be integrated on a chip [1] and Amdahlrsquo;s law[2] was no longer sufficient to describe speed-ups provided by parallelization. Multi-core systems are being accepted in a wide spectrum of disciplines in industry. The use of multi-cores with real-time constraints is still a largely unexplored problem, since, in such systems, ease of integration and predictability are highly sought out. However, due the increase in system complexity, real-time systems producers are begrudgingly accepting the use of multi-core systems due to their ever rising performance. Therefore, better real-time approaches need to be adopted to satisfy their elevated requirements. In real-time systems, the correctness of the system behavior depends not only on the results of its computations, but also on the time at which these results are produced [3]. The schedulability analysis of a system verifies their temporal correctness under a specific scheduling policy.
现代硬件平台设计的趋势已经转向增加处理元件的数量。多核架构的兴起重塑了计算机工程，并确定需要持续的更新。摩尔定律将其重点从晶体管的数量转移到可以集成在芯片上的核心数量[ 1 ]并且Amdahl定律[ 2 ]不再足以描述并行化提供的加速。多核系统正在被工业界广泛的专业领域所接受。具有实时性约束的多核的使用很大程度上仍然是一个尚未探索的问题，因为在这样的系统中，仍在高度寻觅集成和可预测性的便捷性。然而，因为不断提高的性能，实时系统的制造者才不情愿的使用这样越来越复杂的多核系统。因此，需要采用更好的实时方法来满足其提高的要求。在实时系统中，系统行为的正确性不仅取决于其计算结果，还取决于产生这些结果的时间[ 3 ]。系统的可调度性分析在特定调度策略下验证其时间正确性。
In the past, research efforts has been concentrated on scheduling and schedulability analysis of single processor systems. In more recent years, several research works dealt with the problem of scheduling in multi-core systems[4]. In uni-processor systems, the processor switches between multiple jobs[5] whereas in multiprocessor systems, tasks run concurrently in the different processing units of the parallel execution platform.Inthecontextofreal-time scheduling on multi-core systems, one widely used approach is the partitioned scheduling. This approach is based on a two-stage approach going from a global mapping onto the architecture cores to a local scheduling in each core[1]. For such scheduling technique, one should be able to determine:where the task should be executed(mapping) and when the task should be executed with respect to the other tasks running on the same core(uni-processorscheduling).
过去，研究工作主要集中在单处理器系统的调度和可调度性分析上。近年来，一些研究工作涉及多核系统中的调度问题[ 4 ]。在单处理器系统中，处理器在多个作业之间切换[ 5 ]，而在多处理器系统中，任务在并行执行平台的不同处理单元中并发运行。在多核系统的实时调度环境中，一种广泛使用的方法是分区调度。这种方法包括从全局映射到核心的调度和每个核心中的本地调度两个阶段方法[ 1 ]。对于这种调度技术，应该要确定：任务在那个核心执行以及相对于同一核心的其他任务，任务应该什么时候执行。
The complexity involved in finding efficient mapping solutions in multi-core systems has motivated the use of several meta-heuristics [6]. Genetic algorithms (GAs), introduced by Goldberg and Holland [
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
