STAP并行处理系统的调度问题研究

为了研究空时自适应处理(STAP)并行系统中的调度问题,以系统数据和任务为研究对象,以时延和吞吐率为目标函数参数,以均衡性和扩展性为系统设计理念,首先研究了STAP系统的数据划分和任务映射方法。然后提出了任务映射模型,建立了任务流程粗粒度有向非循环图(DAG),进一步分析了STAP系统中的两个重要性能指标。并基于以性能指标为参数的目标函数,研究了STAP系统中的调度策略,提出的五步映射法能够较好地均衡系统负载,满足系统的设计要求。最后给出了一组基于异构处理系统的测试基准和实际STAP系统的实现过程,验证了该研究的有效性。     

并行计算机仿真程序——PCS

本文介绍利用单计算机与C语言开发的在Unix操作系统控制下运行的IP—1并行计算机仿真程序PCS。该程序提供一个多处理机并行程序的仿真执行环境,并在执行过程中能观察某些变量的中间结果。其目的在于辅助并行程序的调试和并行算法的研究。 本文提出了IP—1并行计算机的仿真模型:将多处理机映射到多进程,多路存取存贮器映射到MAM数据数组,纵横开关映射到交换控制函数,并行性映射到并发性及并行运行方式映射到串行运行方式。     

并行仿真计算的任务划分问题研究

本文首先分析总结了并行仿真计算任务的三类任务划分方法：算术运算级划分、程序方程级划分和状态变量级划分，然后重点讨论状态变量级的最优划分问题。文中针对同构型的多处理机系统和多计算机系统，分别建立了仿真计算的性能模型，并求出了系统的最优划分粒度。     

一维云模型映射器设计及其应用研究

通常,云模型的基本原理常用于空间数据挖掘和知识发现。采用云模型不确定性推理方法设计了一种云模型映射器,该映射器在本质上具有非线性映射特性和并行运算功能。文中给出了云模型映射器的结构设计方法,分析了其非线性映射特性和曲线拟合功能,仅需少许修改云模型集合或云模型推理规则,就可以方便、灵活地实现线性映射与非线性映射功能。据此设计了一种智能控制器,将其应用于基于网络QoS变化的直流电机控制系统中,并给出了相关的仿真结果。     

渔用声纳模拟器关键技术的研究

从航海教育和培训的角度出发,为完善航海模拟器,使其能在渔业培训中发挥重要的作用,设计了较合理的鱼群模型和海底模型,并采用点映射的方式正确地反映回波位置信息,对鱼群回波和海底回波进行了模拟;提出了基于噪声强度的灰度级别划分方法,结合图像处理技术以提高渔用声纳模拟器的回波图像效果.软件实现结果表明,该方法能正确仿真渔用声纳的工作原理,能准确表现声纳回波图像,在理论研究及模拟训练领域具有重要的应用价值.     

基于时间Petri网的实时多任务调度方法研究

Petri网是一种模拟和分析的系统工具，能有效地描述并发与并行、同步与异步问题。对时间Petri网在水下航行器制导系统仿真多任务调度中的应用进行了探索和研究。首先介绍了时间Petri网的基本原理，并以水下航行器制导仿真系统为例，将水下航行器制导仿真多任务系统划分为自导子任务、控制子任务、程序弹道子任务、目标运动子任务和指挥导引子任务，在建立和分析时间Petri网模型的基础上，给出资源的束双处理器条件下的最佳调度方案。仿真结果表明，通过该方法完成的多任务调度，能使水下航行器制导仿真系统多任务协调地在双处理器计算机环境下运行，满足水下航行器制导仿真系统分析研究的需求。     

多层次分布实时仿真系统的静态调度策略

针对多层次分布实时仿真系统环境的特点,为了解决任务静态调度问题,提出了一种基于实时性分层的调度策略。该算法结合任务分层和启发式列表调度算法,在映射中同时考虑任务节点计算负载和通信开销映射到系统节点的等效负载,并映射当前最小总等效量到相应的系统节点上,从而获取较小的调度长度。实验结果表明,与交互优先算法相比该算法能提供较优的调度结果;相对于不考虑实时性而言,在调度中存在着一定的"不平衡"。     

基于混合遗传退火算法的并行测试任务调度优化

并行测试任务的优化调度是并行测试技术的核心问题之一。可以充分利用混合遗传退火算法优异的全局最优搜索能力来寻找具有最大并行率的并行任务序列。首先,建立了并行测试任务调度问题的数学模型;给出了并行率的定义,设计了一种满足资源约束与任务时序约束的基因编码方法及相应的遗传退火操作方案。最后,对实例进行仿真实验,结果验证了该算法的有效性及优越性。     

基于守护/控制模式的并行仿真任务分发算法研究

在研究相关并行仿真任务分发和调度方法的基础上,提出了基于守护/控制模式的并行仿真任务分发和调度构建方法,并设计了基于该模式下的一种并行仿真多样本任务分发算法,算法可自动地将仿真样本分发到多台客户机上并行执行,使得在执行仿真时仿真用户并不需要关注样本的分发过程,从而有效提高了仿真多样本的自动分发程度,为并行仿真应用系统的运行提供了高效支持。本算法对类似系统的实现具有重要的参考意义。     

面向连续系统并行仿真的任务调度算法

任务调度是并行分布计算中最具有挑战性的问题之一。如何合理、有效地地进行任务调度,将直接影响到系统的并行效率。本文通过对连续系统仿真程序特点的分析,折衷考虑了负载平衡与通讯延时两方面因素对并计算的不同影响,提出了一种以系统总的开锁最小为目标的启发式调度算法。该算法在我们研制的长缨三号（ＣＨＹ－Ⅲ）并行机上经验证,具有良好的并行效率。     

基于GPU的相位干涉仪FX鉴相算法

针对相位干涉仪测向系统对于大量高速实时信号的处理需求, 设计了基于图形处理单元(graphic processing unit, GPU)的频域互相关(简称为FX)鉴相算法, 完成了相应的并行程序设计, 进行了实时数据的测试验证。为充分发挥GPU强大的浮点运算能力和并行数据处理能力, 将涉及大量并行高速数据计算的核心鉴相算法加载在GPU中, 实现了高速并行数据的相关处理和相位提取; 利用中央处理器(central processing unit, CPU)完成了数据调度、分发和简单的数据处理功能。实验测试结果表明, 在较好地保证鉴相精度的条件下, 本文设计的基于GPU的鉴相算法, 其数据处理速度是基于CPU平台的140倍左右, 鉴相速度明显提升, 较为圆满地实现了实时性、可靠性和准确性的设计初衷。     

带有学习效应和机器可用性限制的排序问题

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。     

MIP formulations and heuristics for solving parallel batching problems

This paper addresses the scheduling problem involving batch processing machines, which is also known as parallel batching in the literature. The presented mixed integer programming formulation first provides an elegant model for the problem under study. Furthermore, it enables solutions to the problem instances beyond the capability of exact methods developed so far. In order to alleviate computational burden, the authors propose MIP-based heuristic approaches which balance solution quality and computing time.     

数字式声纳的多目标跟踪算法及实现

首先介绍了数字式声纳数据综合后置处理的方案,其中数据综合后置处理包括对目标距离、速度和方位的测量,以实现目标搜索、判断。在此基础上,着重讨论了多机动目标跟踪的算法模型及算法实现,引入了当前目标模型,提高了声纳系统中对机动目标的处理能力。根据声纳信号处理的特点,提出了扇环型跟踪门模型并在多DSP阵列系统中实现。最后由系统性能测试的结果可以看出,整套系统能较好地满足设计要求。     

空间科学卫星数据处理框架研究与系统实现

基于我国空间科学战略发展需求，针对我国空间科学先导专项当前在役与未来即将开展的众多卫星任务，对卫星地面段的数据处理框架及关键技术进行研究，提出了一种通用的具有任务级与资源级双层调度引擎的空间科学卫星数据处理技术框架（space science satellite data processing framework, SDPF），设计实现了自动、高效、实时、标准化的空间科学卫星数据处理系统，使得多卫星任务、多载荷数据源的大规模数据的高度复杂的处理过程得以快速并行完成，在数据处理能力、计算资源规划、应对故障的可靠性、灵活性和可拓展性等方面体现出非常好的应用效果，也可为其他领域相关系统的设计提供参考思路。     

高速并行多处理器系统原理及方案

当前,计算机应用领域对计算机的运算处理速度要求越来越高,而提高单机系统的处理能力是有限的,同时系统成本也会很高。因此并行处理技术成为解决这一矛盾的有效方法之一。并行处理系统从硬件角度采看,基本可分为两类;基于低信道容量网络的多计算机系统。这类系统多用于各结点信息藕合比较小、实时性要求不高的松散藕合系统。另一类即是紧藕合的多处理器系统。本文介绍一种已工程实用化了的紧藕合实时多处理器系统。该系统为研究多处理系统的并行算法、任务的实时划分、调度管理等关键技术提供了一个良好的硬件平台及软件环境,该系统可广泛用于要求迭代速率非常高的实时控制与实时仿真系统。     

基于广义粗糙集的不确定条件下的Flow Shop调度

在实际生产调度过程中，加工时间的不确定性是普遍存在的，因此引用广义粗糙变量来表示不确定的工件处理时间，定义粗糙加法运算，precision以及ratio，建立了处理时间不确定性的FlowShop调度问题的精糙规划模型，提出了粗糙遗传调度算法将其应用于调度模型的求解，仿真实验证明了算法的有效性。     

加工时间依赖于资源消耗量的平行机调度问题

研究了一类平行机调度问题,其中假定作业加工时间是资源消耗量的线性减函数,调度的目标是在限定最大完工时间时最小化资源消耗总量. 分析了对应单机问题的最优算法和下界构造方法,进而提出了两个优化策略用于构造模拟退火算法和禁忌搜索算法.考虑了多种最大完工时间限制情形, 构造了大量随机实验数据,对算法解的精确度及计算效率进行了测试.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.     

带有限缓冲区的知识化制造单元无死锁调度

鉴于制造系统无死锁随机调度问题研究的缺乏,在加工时间、工件到达以及产品需求到达均为随机的生产环境下,研究了带有限缓冲区的知识化制造单元无死锁随机调度问题.针对自动机对定量指标描述能力的不足,首先给出了一种费用自动机概念.在同时考虑工件加工、库存以及缺货费用的情况下,采用无限时域折扣准则下马尔可夫链建立了单元的费用目标函数,通过一致化技术对目标函数进行离散化处理,得到目标函数的随机动态规划模型,分析并证明了单元最优目标值函数的性质.为了克服离散状态空间组合所产生的维数灾问题,提出了一种基于仿真和函数逼近的启发式近似动态规划算法对模型进行求解.在上述研究基础上,构建了一种单元无死锁随机调度策略,以保证单元安全高效地运行.最后,通过实例研究对无死锁调度策略进行了验证.     

无重叠区的两抓钩周期性排序问题的一个搜索求解法

在当今的自动化制造系统中,计算机控制的抓钩的排序直接影响系统的生产率.本文研究了产品在生产线两端装载和卸载的电镀线的周期性抓钩排序问题,目标是极小化生产周期.本文把生产线分成无重叠的两部分,并给每部分分配一个抓钩,构成一个无重叠两抓钩周期性排序问题.为了求解该问题,提出了一种基于线性规划模型和禁忌表的搜索算法.这个算法使用测试的周期长度作为控制参数以产生不同的运送顺序,对每个给定的运送顺序和抓钩分配,用线性规划模型求得子问题的最优解.在搜索中,为了避免相同序列的子问题模型的求解,采用了禁忌表.量化的示例表明所使用的方法是高效的.