改进元启发式算法以将独立任务映射到异构内存受限系统

### 改进元启发式算法以将独立任务映射到异构内存受限系统 #### 1. 引言 在异构系统中，将独立任务映射到处理器是一个重要问题。采用主从方案，任务由一个主处理器生成并发送到从处理器进行处理，处理结果再返回给主处理器。以往关于主从方案最优映射的研究存在一定限制，且未考虑内存约束。 每个任务有计算成本和内存需求，系统中的处理器速度和内存容量不同，这对任务分配形成了限制。目标是找到一种任务映射方式，使总执行时间最短。一般情况下，寻找最优映射是一个NP问题，因此启发式方法可能更为合适。之前已提出一些元启发式算法，如遗传算法（GA）、分散搜索（SS）、禁忌搜索（TS）和GRASP（GR），本文将对这些算法进行改进，以减少任务映射时间并获得更好的解决方案。 #### 2. 调度问题 以固定算术成本且无深度通信的调度问题为例。给定t个任务，其算术成本为$c = (c_0, c_1, ..., c_{t - 1})$，内存需求为$i = (i_0, i_1, ..., i_{t - 1})$；p个处理器，执行基本算术运算的时间为$a = (a_0, a_1, ..., a_{p - 1})$，内存容量为$m = (m_0, m_1, ..., m_{p - 1})$。任务到处理器的映射为$d = (d_0, d_1, ..., d_{t - 1})$（$d_k = j$表示任务k分配给处理器j），且需满足$i_k ≤ m_{d_k}$。目标是找到d，使得下式取得最小值： $min_{{d/ i_k≤m_{d_k} ∀k = 0,1,...,t - 1}} max_{{j = 0,1,...,p - 1}} \left\{a_j \sum_{l = 0,1,...,t - 1; d_l = j} c_l \right\}$ 该式表示在满足内存约束的映射中，找到使各映射中耗时最长的处理器时间最短的映射。 由于可能的分配数量最多为$p^t$（考虑内存约束后数量可能减少），通过生成所有可能映射来解决问题在合理时间内不可行，因此考虑使用启发式方法获得近似解。 #### 3. 元启发式算法在调度问题中的应用 考虑将遗传算法（GA）、分散搜索（SS）、禁忌搜索（TS）和GRASP（GR）这四种元启发式算法应用于上述调度问题。从相同视角分析这些算法，识别通用例程和元素表示。目标是获得与最优解接近的映射，同时减少分配时间。通用的元启发式算法方案如下： ```plaintext Initialize(S); while not EndCondition(S) do SS = ObtainSubset(S); if |SS| > 1 then SS1 = Combine(SS); else SS1 = SS; end SS2 = Improve(SS1); S = IncludeSolutions(SS2); end ``` 各函数在不同元启发式算法中的工作方式如下： - **Initialize**：为初始集合S中的每个个体分配任务到处理器，分配概率与处理器速度成正比。 - GA：使用大量初始分配种群。 - SS：S中的元素数量较少，可能比GA耗时更短。 - TS：S中只有一个元素。 - GR：每次迭代评估每个候选者的成本，选择一些候选者纳入解决方案集。 - **ObtainSubset**：随机选择一些个体。 - GA：适应度函数（式1）更好的个体被选中的可能性更大。 - SS：可以选择所有元素进行组合，也可以选择最佳元素与最差元素组合。 - TS：由于|S| = 1，此函数不需要。 - GR：从解决方案集中随机选择一个元素组成集合SS（|SS| = 1）。 - **Combine**：对选中的个体进行交叉操作，得到SS1。 - GA、SS：个体可以通过不同方式交叉，例如交换一半映射得到两个后代。 - TS、GR：此函数不需要。 - **Improve**： - GA：选择一些个体进行变异操作，以增加种群多样性，避免陷入局部最优。 - SS：使用贪心方法，评估每个组件中p个可能处理器（考虑内存约束）得到的元素的适应度值，在邻域中寻找更好的元素。 - TS：分析当前元素邻域中的一些元素，排除禁忌列表中的元素。 - GR：使用局部搜索改进选中的元素，可以使用贪心方法或分析邻域中的所有元素。 - **IncludeSolutions**：选择SS2中的一些元素纳入S，用于下一次迭代。 - GA：将原始集合中的最佳个体、其后代和变异得到的个体纳入下一个S。 - SS：选择最佳元素以及与它们分散的一些元素，避免陷入局部最小值。 - TS、GR：将分析得到的最佳元素作为下一个解决方案。 - **EndCondition**：GA、SS、TS、GR的收敛准则可以是最大迭代次数，或者种群中最佳适应度值在多次迭代中不变。 #### 3.1 元启发式算法的基本实验调优 进行了不同任务和系统配置的实验，结果相似。实验配置如下：每个任务的大小随机生成在1000到2000之间，算术成本为$n^3$，内存需求为$n^2$。系统中处理器数量与任务数量相同，基本算术运算成本随机生成在0.1到0.2微秒之间，每个处理器的内存为最大任务所需内存的一半到一倍半之间。使用以下参数值获得了初步结果，相近参数值的结果相似： - **GA**： - Initialize：种群有80个元素，元素初始时根据处理器速度随机分配任务。 - Combine：每对元素交叉时交换一半组件，每次组合将最佳父代和最佳后代纳入种群。 - Improve：变异概率为1/5。 - EndCondition：最大迭代次数为800，未改进最优解的最大迭代次数为80。 - **SS**： - Initialize：S有20个元素，初始化方式与GA相同。 - Combine：组合方式与GA相同。