DNA并行计算中的B-树数据结构的设计与实现

DNA分子特性使得DNA计算具有极大的存储密度和高度的计算并行性。不管何种计算模型,DNA分子的选择和DNA编码都十分重要。提出了DNA计算中的B-树的数据结构设计方法。首先给出了B-树定义及其操作的形式化描述,接着介绍了本计算模型采用的3D结构DNA分子——k-arms分子结构,详细给出了一棵m阶B-树的构造步骤,最后实现了其查找、插入和删除等操作。提出了DNA分子计算的3D结构和分治策略,具有一定的可扩展性和并行性,对DNA计算的其他模型有参考价值。     

并行机实时调度问题的LR&CG算法

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.     

Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning

We address an unrelated parallel machine scheduling problem with R-learning, an average-reward reinforcement learning (RL) method. Different types of jobs dynamically arrive in independent Poisson processes. Thus the arrival time and the due date of each job are stochastic. We convert the scheduling problems into RL problems by constructing elaborate state features, actions, and the reward function. The state features and actions are defined fully utilizing prior domain knowledge. Minimizing the reward per decision time step is equivalent to minimizing the schedule objective, i.e. mean weighted tardiness. We apply an on-line R-learning algorithm with function approximation to solve the RL problems. Computational experiments demonstrate that R-learning learns an optimal or near-optimal policy in a dynamic environment from experience and outperforms four effective heuristic priority rules (i.e. WSPT, WMDD, ATC and WCOVERT) in all test problems.     

一种基于智能调度的可扩展并行强化学习方法

针对强化学习在大状态空间或连续状态空间中存在的“维数灾”问题,提出一种基于智能调度的可扩展并行强化学习方法——IS-SRL,并从理论上进行分析,证明其收敛性.该方法采用分而治之策略对大状态空间进行分块,使得每个分块能够调入内存独立学习.在每个分块学习了一个周期之后交换到外存上,调入下一个分块继续学习.分块之间在换入换出的过程中交换信息,以使整个学习任务收敛到最优解.同时针对各分块之间的学习顺序会显著影响学习效率的问题,提出了一种新颖的智能调度算法,该算法利用强化学习值函数更新顺序的分布特点,基于多种调度策略加权优先级的思想,把学习集中在能产生最大效益的子问题空间,保障了IS-SRL方法的学习效率.在上述调度算法中融入并行调度框架,利用多Agent同时学习,得到了IS-SRL方法的并行版本——IS-SPRL方法.实验结果表明,IS-SPRL方法具有较快的收敛速度和较好的扩展性能.     

提升大规模集群上并行计算软件系统可靠性和服务性的方法与实践

大规模集群上的并行计算软件需要具备处理部分节点、网络等失效的容错能力,也需要具有易于管理、维护、移植和可扩展的服务能力。针对星形计算模型,研究和开发了一套并行计算框架。利用调度节点内部的可变粒度分解器、相关队列等方法,实现了全系统容错,且具有较好的易用性、可移植性和可扩展性。系统目前可以实现300TFlops计算能力下连续运行超过150h,而且还具有进一步的可扩展能力。     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

基于动态状态树的回溯算法

介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.     

并行卡尔曼滤波器的多信道序列规划算法

针对基于卡尔曼滤波器的并行序列规划问题,本文提出了一种基于多信道的改进算法,在规划各进程所对应传感器的测量信息传输序列,以使相应滤波器的状态估计误差协方差满足给定指标的同时,尽可能减少通讯信道占用.文中论证了基于夹挤方法的周期算法,以提高计算进程传输周期的效率;改进了基于缓存的离线序列规划算法,以适应多信道传输的情景;设计了在线序列调整算法,利用空闲信道进行传输失败后的数据复发,快速调整序列以适应指标变化的需求.算法的运行效果将通过仿真实验进行验证与分析.     

基于策略梯度强化学习的高铁列车动态调度方法

高速铁路以其运输能力大、速度快、全天候等优势,取得了飞速蓬勃的发展.而恶劣天气等突发事件会导致列车延误晚点,更甚者延误会沿着路网不断传播扩散,其带来的多米诺效应将造成大面积列车无法按计划运行图运行.目前依靠人工经验的动态调度方式难以满足快速优化调整的实际要求.因此,针对突发事件造成高铁列车延误晚点的动态调度问题,设定所有列车在各站到发时间晚点总和最小为优化目标,构建高铁列车可运行情况下的混合整数非线性规划模型,提出基于策略梯度强化学习的高铁列车动态调度方法,包括交互环境建立、智能体状态及动作集合定义、策略网络结构及动作选择方法和回报函数建立,并结合具体问题对策略梯度强化学习(REINFORCE)算法进行误差放大和阈值设定两种改进.最后对算法收敛性及算法改进后的性能提升进行仿真研究,并与Q-learning算法进行比较,结果表明所提出的方法可以有效地对高铁列车进行动态调度,将突发事件带来的延误影响降至最小,从而提高列车的运行效率.     

基于递阶遗传算法的并行多机调度优化

针对最小化完工时间的等同和非等同并行多机调度一类问题，提出了一种递阶遗传算法。该算法根据问题的特点，采用一种递阶编码方案，此编码与调度方案一一对应。用递阶遗传算法优化并行多机调度不需设计专门的遗传算子，操作简单。计算结果表明，递阶遗传算法是有效的，能适用于大规模等同和非等同并行多机调度问题。     

蚁群算法求解非等同并行机调度问题的研究

针对非等同并行机服务调度问题,以机场除冰调度服务为背景并以最小化旅客延误数为目标,提出了一种改进的蚁群算法。该算法根据调度模型的特点,充分考虑模型的约束条件并运用了一种改进的信息素更新策略求解并行机调度问题。仿真结果表明,改进的蚁群算法收敛速度快且结果较优,明显优于FIFO算法,适合求解非等同并行机调度问题。     

A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Recently, a growing number of scientific applications have been migrated into the cloud. To deal with the problems brought by clouds, more and more researchers start to consider multiple optimization goals in workflow scheduling. However, the previous works ignore some details, which are challenging but essential. Most existing multi-objective workflow scheduling algorithms overlook weight selection, which may result in the quality degradation of solutions. Besides, we find that the famous partial critical path (PCP) strategy, which has been widely used to meet the deadline constraint, can not accurately reflect the situation of each time step. Workflow scheduling is an NP-hard problem, so self-optimizing algorithms are more suitable to solve it.In this paper, the aim is to solve a workflow scheduling problem with a deadline constraint. We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning (RL) called DCMORL. DCMORL uses the Chebyshev scalarization function to scalarize its Q-values. This method is good at choosing weights for objectives. We propose an improved version of the PCP strategy calledMPCP. The sub-deadlines in MPCP regularly update during the scheduling phase, so they can accurately reflect the situation of each time step. The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline. Finally, we use four scientific workflows to compare DCMORL and several representative scheduling algorithms. The results indicate that DCMORL outperforms the above algorithms. As far as we know, it is the first time to apply RL to a deadline constrained workflow scheduling problem.     

基于多核处理器并行系统的任务调度算法

针对多核处理器并行系统的特点,提出了相应的任务调度算法,该算法在任务调度之前加入了任务分配技术,通过合理的任务分配,可有效减少多个处理器间的通信开销,使任务调度效率更佳.仿真实现了该算法,并通过实验数据证明了该算法的优越性.     

并行扫描转换结构中的状态管理

扫描转换为图形流水线的核心部分,许多高性能的图形硬件都是采用并行的扫描转换结构。现代GPU(graphic processing unit)用于高性能计算时,主要依靠其极大的系统吞吐率,但是用基于传统的状态管理方法维持命令顺序性时会造成处理单元的停顿,降低系统的吞吐能力。提出一种新的状态管理方法,将命令分为计算与控制两类,对于控制类的命令由状态处理单元生成状态掩模(state-mask),减少了状态管理中的广播通信,降低了保持命令顺序性和状态管理的复杂性。仿真结果表明所提出状态管理方法同传统的状态管理方法相比,在游戏等后端状态变化明显的图形应用中,扫描引擎利用率提高了5%~9%。     

A phased reinforcement learning algorithm for complex control problems

In this article, a phased reinforcement learning algorithm for controlling complex systems is proposed. The key element of the proposed algorithm is a shaping function defined on a novel position–direction space. The shaping function is autonomously constructed once the goal is reached, and constrains the exploration area to optimize the policy. The efficiency of the proposed shaping function was demonstrated by using a complex control problem of positioning a 2-link planar underactuated manipulator.     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。     

Plane级的闪存固态盘并行调度算法

为有效缓解固态盘的存储瓶颈问题,针对闪存固态盘内部芯片的工作原理和物理特性,将并行调度技术引入闪存固态盘的闪存转换层(FTL)的设计中,设计并实现了一种plane级的并行调度算法,基本方法就是将一个读写请求分解成多个段,在多个plane上并行的执行,通过更均衡的分配I/O负载,可以显著提高闪存固态盘的整体读写性能。通过设置不同的芯片参数进行了模拟与测试,实验结果表明,采用并行调度技术可以有效提高闪存固态盘中存储芯片之间的并行度,以及芯片内部各个单元之间的并行度,闪存固态盘的读写延时均有较大改善。     

A scalability test for parallel code

Code scalability, crucial on any parallel system, determines how well parallel code avoids becoming a bottleneck as its host computer is made larger. The scalability of computer code can be estimated by statistically designed experiments that empirically approximate a multivariate Taylor expansion of the code's execution response function. Each suspected code bottleneck corresponds to a first-order term in the expansion, the coefficient for that term indicating how sensitive execution is to changes in the suspect location. However, it is the expansion coefficients for second-order interactions between code segments and the number of processors that are fundamental to discovering which program elements impede parallel speedup. A new, unified view of these second-order coefficients yields an informal relative scalability test of high utility in code development. Discussion proceeds through actual examples, including a straightforward illustration of the test applied to SLALOM, a complex, multiphase benchmark. A quick graphical shortcut makes the scalability test readily accessible.