关键词： 调度算法   工作流生成   可视化模型  

摘要： 近年来,由于多核处理器、云计算的大力发展,人们开始认识到调度算法的重要性。现今,单处理器环境下的任务调度算法已逐渐成熟,在各方面都有了广泛的应用。但我们若是为了贪图方便而直接将这些调度算法不加改变的转移到多资源环境下应用,最终效果可能不达预期。为了给科研人员提供一个较好的算法比较工具去帮助他们分析问题,我们尝试构建一个集工作流生成、数据分析、结果展示于一体的工作流调度模拟器VWGSim。VWGSim主要有两大核心部分:一是在指定参数下的工作流随机生成,二是以可视化界面的形式展现算法调度结果。算法研究者可以以最优调度方案结果为参考找出其调度算法的缺陷,为算法改进指出明路。借助VWGSim的“力量”,我们对多处理器环境下的多工作流实时调度算法做了进一步的探讨研究,并针对于该问题的两个层面提出了三种行之有效的改进算法。在作业级层面,我们提出了MCSW算法。对于同一批作业,如何更加公平的调度同时刻提交的作业也是值得探讨的问题,MCSW算法便是一种基于合并策略的公平调度算法。在任务级层面,我们提出了DCBF算法和DCMG算法。DCBF算法旨在不违反任务截止时间的基础上找到任务长度和资源空隙比值最大的位置,DCMG算法旨在不违反任务截止时间的基础上找到与资源空隙紧邻的前一任务之间产生空隙最小的位置。本文所有实验的测试用例都是通过VWGSim生成的。我们利用这些测试用例将MCSW算法、DCBF算法、DCMG算法和它们的对比算法进行比较,证明了它们在自己对应的调度层面上都具有较好的处理器利用率和作业成功率。

关键词： 多处理器   可调度性   干扰   DAG任务模型   自挂起  

摘要： 实时系统因其突出的实时性和可靠性被广泛应用于社会生产中的各个领域。随着物联网技术的不断成熟以及工业4.0的逐步推进,实时系统的发展正经历着质的改变。面对日益复杂的现实需求,实时系统在保证其高响应、高可靠特性的基础上,一方面面临着高性能、高集成的现实需求,另一方面,由于应用场景对其能耗、体积等因素的严格约束,使得现代实时系统的开发面临着多种压力。多处理器平台的飞速进步,为实时系统的开发与设计提供了新的思路。为保证实时系统的实时性和可预测性,实时调度算法发挥了极其重要的作用。全局EDF(Earliest Deadline First)调度算法因其出色的调度性能受到众多学者的关注,同时在工业界也被广泛使用。然而,目前针对全局EDF可调度性分析的研究中,大量的研究工作都以顺序编程模型为基础。随着多核处理器的广泛使用,编程范式正转向细粒度的线程级范式。本文主要研究在多核强实时系统中使用支持线程级并行的DAG(Directed Acyclic Graph)任务模型时,全局EDF调度算法的可调度性问题。本文主要研究内容为以下两个方面。(1)研究在忽略DAG任务中线程的自挂起状态时,全局EDF调度算法的可调度性问题。本研究提出了一种基于图结构的全局EDF可调度性测试算法。通过修正任务节点的执行窗口,考虑任务的DAG结构特征,提出一种对任务间干扰和任务内干扰具有更高计算精度的可调度性测试算法。实验结果表明,本研究提出的算法在保证具有较高识别率的同时,使可调度性测试结果更加符合实际情况。(2)研究在明确考虑DAG任务中线程的自挂起状态时,全局EDF调度算法的可调度性问题。本研究提出了一种明确考虑DAG任务中线程自挂起状态的全局EDF可调度性测试算法。通过对任务图结构进行多次扩展,在分析任务间干扰和任务内干扰时,分别对任务的工作负载和挂起负载进行定量研究,提出一种具有较高识别率的可调度性测试算法。

关键词： Computer engineering  

摘要： Chip Multi-Processor (CMP) platforms, well-established in the server, desktop and embedded domain, succeeded in overcoming the power consumption and heat dissipation bottlenecks by integrating multiple cores, less complex and powerful than their single-core ancestors, in a single die. A major issue induced by the design of the CMPs is contention for the shared resources of the platform, Last Level Cache (LLC) and main memory bandwidth. Applications, running concurrently on the cores, compete with each other for the shared resources, and are subject to performance degradation. The way applications are assigned to the CMP, is crucial for the overall performance of the system. A scheduling policy that accounts for contention will bring high performance speed-ups, whereas an agnostic one will generate unpredictable contention conditions. For this reason the significance of the scheduler has been elevated, as it is the component that determines which applications utilize the resources each time period. In this thesis, we address cross-core interference on CMP platforms, by designing scheduling policies that improve performance and fairness. We deal with contention in three ways. In our first approach, we incorporate the notion of progress in order to balance unfairness among the applications of the workload. Performance degradation is not evenly distributed and progress greatly varies among them. In order to provide a fair execution environment, we monitor, at run-time, applications assigned to the CPU and prioritize them based on the extent at which they are affected by contention. In our second approach, we target performance by mitigating contention on shared resources. It is necessary to decide, out of all the possible application schedules, the one that generates the least amount of resource interference. To achieve that, the first indispensable step is to extract an interference profile for the applications executed on the CMP. We accomplish that by applying pressu

关键词： 多处理器任务调度   柔性流水车间   运输时间   机器可用性   GA&IGP   HGA  

摘要： 随着“工业制造4.0”概念的提出,制造业在面临机遇的同时也遭遇了日趋激烈的竞争现状。如何提高生产效率和服务质量成为制造企业关注的重点。生产调度作为制造企业运作的核心,进而成为了学术界和工程界研究的热点。柔性流水车间调度问题(the Flexible Flow-shop Scheduling Problem,FFSP)最初是基于石油和化工行业提炼出来的,因此有较强的工业应用背景,在大部分的制造企业(钢铁、制药、化工)、集装箱搬运、装配、运输等系统中都有FFSP结构的存在。本文研究的带多处理器任务的FFSP是将多处理器任务与柔性流水车间环境结合起来,问题中任一种或多种特征约束的简化都可能构成其他不同的典型调度模型,因此研究具有广义性和挑战性本文研究的带多处理器任务的FFSP,考虑了机器故障、工件动态到达和运输时间等实际生产约束条件。以往文献中关于带多处理器任务的FFSP取得目标值多为最小化最大完工时间,该目标值衡量了工件总的完工时间,值越小代表生产效率越高,目标值为最小化总加权完工时间的文献也受到学者研究的重视。因此,本文首先针对运输时间的带多处理器任务的FFSP取目标值为最小化最大完工时间,利用GA&IGP(Genetic Algorithm&Iterative Greedy Procedure)算法对模型进行求解。然后针对带时间窗的带多处理器任务的FFSP取目标值为最小化总加权完工时间,利用HGA(Hybrid Genetic Algorithm)算法进行求解。本文采用的算法,主要是基于贪婪算法和自适应改进思想对遗传算法进行改进。首先,基于研究问题的复杂性,工件在加工过程中不仅需要确定工件排序还需要安排足够数量的机器进行加工,因此设计了基于工件-机器的二维编码方案,利用JAP-RSIM工件安排机制产生初始可行解。然后进行基于工件-机器同步交叉和变异的新解更新过程,对新解进行适应度值计算和判断后,执行贪婪算法的新解调整和重建操作,进而形成了GA&IGP融合优化策略。在GA&IGP算法程序的基础上,引入自适应改进思想,对变异概率和交叉改进进行自适应改进,形成基于遗传算法的HGA算法。最后利用仿真实验,通过测试多组不同规模问题,对比了GA、IGP、GA&IGP三种算法在求解同一约束条件的带多处理器任务FFSP时,GA&IGP求解质量最优,适合于求解大规模问题。而且还对比了GA、GA&IGP、HGA三种不同改进程度的遗传算法在求解同一约束条件的带多处理器任务FFSP时,HGA求解质量优于GA&IGP和GA。证明了引入贪婪算法对遗传算法改进能避免过早收敛的缺点,通过自适应改进能更进一步提高遗传算法的求解能力。

关键词： 振动数据采集   多通道同步   希尔伯特-黄变换   位移重构  

摘要： 振动数据采集是实现设备状态监测与相关控制的重要环节。振动信号反映了结构或设备运行的状态,通过设计振动数据采集系统,实现振动信号的采集,分析振动信号得到的结果可作为结构健康监测的重要评价指标,或者设备控制的重要反馈变量。研究振动信号的时频特性,提取特征信息,利用振动加速度信号在时域中二次积分的方法得到动态位移响应。采集系统充分考虑FPGA和ARM各自的优点,采用FPGA与ARM的多核架构设计方案。考虑到需要对多路传感器同时采集,采集系统设计了十二路同步采集接口,并通过前端模拟电路的配置,实现对不同传感器接入类型的匹配;系统采用双ADC设计,每个ADC完成六个通道同步采样,FPGA同时控制两个ADC的启动转换实现十二个通道同步采样;采用以太网接口实现采集系统与服务器或上位机之间的通信,完成采样数据的实时传输及服务器对采集系统的参数设置;考虑到采集系统的现场离线工作场景,采用Micro SD卡实现在低速采样模式下采样数据的本地存储;采集系统的RS485接口可实现多个采集系统之间的同步,构建分布式同步数据采集系统。通过先功能仿真后硬件系统验证的方法,完成FPGA内部各功能模块的设计。FPGA根据服务器发送的控制命令字,在FPGA内部构建参数设置寄存器,实现对采样模式、采样率等参数的设置;根据ADC工作时序,实现对ADC的采样控制并完成对两路ADC的采样数据读取;利用SDRAM特点,FPGA和SDRAM实现对采样数据的深度缓存设计;通过构建异步FIFO,实现FPGA与ARM之间的高速数据通信。ARM采用抢占式多任务实时操作系统(RTOS)实现多任务管理。采用轻量级互联网协议(LwIP)实现采集系统与服务器之间的网络通信;通过对ARM高速数据接口FSMC的配置,完成对FPGA内部异步FIFO的读取与参数寄存器的写入;通过文件操作系统(FatFS)实现对Micro SD卡的文件读写操作。通过采集标准信号源验证了采集系统功能设计的正确性、实时性和可靠性;通过采集的振动台数据验证了希尔伯特-黄变换(HHT)算法在动态非平稳数据处理上的优越性,验证了加速度时域中二次积分重构位移的可行性;通过采集的桥梁振动响应数据参照视频记录分析了桥梁在不同交通流下的时频特性与动态位移响应,为桥梁维护与预警提供重要的依据。

关键词： 可穿戴   异构多核   任务调度   关键任务   可靠性   DAG模型  

摘要： 随着智能穿戴设备在生活、军事和医疗等领域的应用愈加广泛,如何提高嵌入式系统的可靠性以更好地适用于更多的应用场景,成为了一个值得研究的问题。本文首先对可穿戴设备的应用场景进行了分析,结合现有的一些容错调度算法详细分析了可穿戴设备在实际应用场景中所面临的问题,并实现了面向关键任务的容错调度平台,在软件层面为关键任务提供容错保护。结合可穿戴设备对体积、功耗和运行效率的需求,搭建了RK3399芯片与Zynq ZC706相结合的硬件平台,实现了以边缘检测算法与图像增强算法为例的任务处理模块。实现了基于双模冗余的容错调度模块,为关键任务提供可靠性保证。并且结合异构多核架构的特点提出了一种处理器之间的任务同步机制,通过该机制对容错调度算法进行了改进,在不影响容错性能的同时,缩短了容错算法的运行时间。同时,对基于DAG的任务模型从任务可靠性的角度进行了分析,指出了基于DAG模型的计算任务中的子任务之间存在着时序依赖。这些子任务在运行时发生的瞬态故障会产生连锁反应,对系统的可靠性造成不良的影响。针对这一问题,提出了基于聚类的容错调度算法和平衡系数的概念,通过将聚类算法与表调度算法进行结合,为DAG图中不同的任务提供不同的容错策略,以提高调度算法的性能。最后,对改进前后的容错调度算法进行了对比实验。实验结果表明,在基于RK3399+Zynq的异构多核架构并以边缘检测与图像增强为计算任务的实验平台中,实现了具有稳定有效容错性能的调度模块。同步机制在对容错性能无明显影响的同时,有效减少了任务的总运行时间,并且优化了系统中不同核心的负载。面向DAG模型的容错调度算法在随机注入相同数目故障的情况下,与表调度算法相比,有效降低了在处理具有低平衡系数计算任务时的总运行时间。

关键词： 集群系统   高性能计算   并行处理   遥感数据  

摘要： 高性能集群并行处理技术已成为海量遥感数据快速处理的重要方法。文章给出了一套精简的遥感数据高性能集群处理系统的结构,阐述了系统的并行处理机制,并从遥感数据并行处理策略、作业与资源管理系统、可视化流程定制、高性能计算编程模型等多个方面对集群式遥感数据处理中的关键技术进行了分析与说明。该研究对遥感处理专业人员和高性能集群系统的设计和开发人员具有一定的参考作用。

关键词： 多处理器   磁悬浮轴承   控驱一体集成架构  

摘要： 磁悬浮轴承因其优异性能是高性能转子系统的理想支承。常规磁悬浮控制系统采用控制器与电流驱动器分别实现位置环和电流环的控制,通过模拟信号传输来实现控制信息的交互,易受干扰且成本较高。提出一种应用于磁悬浮轴承的控驱一体架构,采用双DSP的并行处理方案,实现针对5自由度磁悬浮转子的控制;采用双端口SRAM替换常规DA-AD的方案用于位置环和电流环之间的信息交互;根据双口SRAM的控制时序设计了相应的软件控制流程。试验表明,所提出的多处理器磁悬浮控制系统架构,能有效实现电流环和位置环的双环控制,实现转子系统的稳定悬浮,该架构的有效性得到了证明。

关键词： 实时系统   多处理器   全局EDZL算法   可调度性判定   最大连续忙区间  

摘要： 可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。分析在多处理器实时系统中全局EDZL算法的任务需求,考虑了带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。通过构造大量实时任务集,对不同的判定方法进行了实验,检查通过可调度性判定的任务集数量。实验结果表明,这种方法在多处理器实时系统中是一种更为紧密的可调度性判断方法。

关键词： 多处理器嵌入式软件   全数字仿真测试平台   DDS   软件测试  

摘要： 研究了针对多处理器嵌入式软件的全数字仿真测试平台开发技术,该技术基于DDS(数据分发服务),设计实现了基于通道的系统模型,通过将被测软件分布在局域网多个节点,实现了基于多处理器嵌入式软件的全数字仿真测试平台。该平台准确同步每个核的运行时间,并模拟各处理器板之间的硬件接口,使基于多处理器的嵌入式软件测试摆脱了半实物环境的制约,提高了测试有效性,缩短了测试周期。