栅格数据处理中邻域型算法的并行优化方法

随着并行计算的成熟,众多数据密集型的栅格处理算法亟需利用并行计算来缩减执行时间.针对其中一类邻域型算法,构建了用于估计是时间代价的串行/并行时域模型,分析了各个组成的代价影响因素,提出了降低数据I/O代价的并行I/O方法和降低数据通信代价的光圈预测方法.实验证明,所提的两个优化方法可以使邻域型栅格处理算法的并行程序更加充分地利用并行计算资源,进而在一般并行化的基础上进一步提升其并行性能.     

矢量多边形并行栅格化数据划分方法

针对多边形并行栅格化中的负载不均衡问题提出一种新的数据划分方法,主要包括:迭代计算划分线的位置,在每次迭代中保证分块间的计算量大致均衡,完成数据划分、实现负载均衡;提出基于二叉树的划分结果融合策略,以解决跨边界多边形的融合问题。在多核CPU环境下实现并行算法,选用多个典型土地利用现状数据集进行测试。结果表明:针对不同类型多边形数据集,所提方法较传统方法可获得更高的并行加速比和更好的负载均衡;针对大数据量数据集,以多边形节点数为度量标准可更精确地估算分块计算量,从而更好地实现负载均衡。     

一种面向完成时间与负载均衡的任务调度算法

公共计算环境作为新一代舰艇信息系统集成环境,具有统一架构、资源共用、可扩展等优点,是未来舰艇信息化发展的关键。公共计算环境本质是云环境,任务调度中的完成时间和负载均衡对公共计算环境的整体性能有重要影响。面向优化完成时间和负载均衡两个主要问题,采用了基于改进蚁群优化算法的任务调度算法和负载修正系数,融合非支配遗传算法(NSGA-Ⅱ)中快速非支配排序的方法进行多目标优化,生成最优解的Pareto前沿。使用CloudSim平台进行仿真模拟,实验结果表明,在负载均衡和完成时间目标上,提出的面向完成时间与负载均衡的蚁群算法(TL-ACO)与NSGA-Ⅱ相比性能更优异。     

栅格地理数据并行格式转换引擎

如今大规模地理数据正在社会各个部门和组织中迅速积累,但是由于部门利益和历史沿袭等原因,大规模地理数据共享仍然极具挑战,相应共享技术需求仍然极其旺盛。作为地理数据共享的基础方式之一,传统单机地理数据格式转换技术,一方面受限于磁盘读写及带宽瓶颈,另一方面面对日趋庞大的数据规模,已很难满足实际应用需求。因此提出一种针对栅格地理数据的并行格式转换引擎,采用高性能计算集群环境支持大规模栅格地理数据转换共享,大幅降低了大规模栅格地理数据转换过程的时间成本。栅格地理数据并行格式转换引擎采用基于公共接口的设计理念,框架灵活、具有良好的扩展性,支持地理数据格式的读写自定义以及新数据格式添加,能够实现接入数据格式间的任意两两转换。为验证引擎框架及其处理效率,在Lustre并行集群环境下以格网数据交换格式(国家地理空间数据交换格式)向常见栅格地理格式的转换为示例进行了测试实验。结果表明,栅格地理数据并行格式转换引擎能够在8个节点Lustre集群中达到7.54的良好并行加速比。     

基于栅格分层的逐栅格汇流算法并行化研究

分布式水文模型中的逐栅格汇流算法计算量大,需要借助并行计算以满足大流域长历时模拟的要求。针对目前鲜有对基于隐式有限差分的逐栅格汇流算法进行并行计算研究的情况,基于栅格分层的思想提出一种适用于共享内存并行计算环境的逐栅格汇流并行算法。该算法首先根据流向进行栅格分层,使同一层中栅格的计算相互独立,然后将同一层中栅格的计算任务分配到多个计算单元并行计算。采用C++编程语言与OpenMP并行编程库实现了该算法,并选择河北省清水河流域为实验区,在不同数据规模(30m、90m、270m分辨率)、不同核数(2～20个)以及不同栅格分层方法的情况下对算法性能进行了测试。实验结果表明本文提出的并行算法具有较好的加速比和并行效率,且并行效率随数据规模的增大而增大。栅格分层方法对算法并行性能有明显影响,从上到下的分层方法比从下到上的方法具有更高的并行效率。     

多光源并行化算法的实现

针对在绘制具有真实感的图形中光照处理模块串行处理速度慢的问题,提出多光源光照算法的并行化,采用负载均衡的并行策略,重新优化计算模型,单独计算环境光、散射光、镜面光及衰减因子后叠加在一起。计算不同的PE(处理单元)个数使用了不同的分配方案来提高处理速度。实验结果表明,将多光源光照算法并行化,可充分利用资源,发挥多核处理器的处理能力,提高了资源利用率。     

基于复杂区域栅格化的传感器网络优化部署

为实现对复杂区域的优化部署,对部署区域进行了栅格化处理,引入重点保障区域、优势部署区域等概念,改进了网络保障能力模型,给出了其栅格化表达式,并运用遗传算法对模型进行求解。仿真结果表明,该方法具有易于工程实践、求解精度适中、可对复杂区域的传感器网络进行优化部署的优点。     

一种面向多核处理器的高效并行PCA-SIFT算法

提出一种面向多核处理器的并行PCA-SIFT算法,采用数据级并行方法实现并行的特征提取和特征点匹配,将计算任务分配到各个DSP核并行处理,充分开发多核处理器的多级并行性.实验结果表明,并行PCA-SIFT算法对各种不同图像形变的图像具有良好的适应性,具有接近串行PCA-SIFT算法的图像匹配能力,平均加速比达3.12.     

面向网络化无人机集群的计算换通信分布式任务调度方法

针对网络化无人机集群任务自主协同问题以及市场竞拍法的优缺点,提出“计算换通信”思想及其相应的分布式任务调度方法。通过对显式和隐式冲突任务的分析,建立任务相关智能体集合。提出基于任务抑制的局部优化方法,用于提前消解部分任务冲突,以减少算法迭代次数。设计基于历史竞标信息的智能体位置推断法,为局部优化提供必要的信息输入。基于组网仿真平台与集群救援场景开展蒙特卡罗仿真实验,结果表明,相比于市场竞拍法中具有代表性的基于共识的捆绑算法和性能影响算法,所提方法能够获得更少的迭代次数、更短的收敛时间以及更优的调度性能。     

一种结合Turbo均衡和栅格OFDM系统的T-LOFDM系统

在双扩散信道环境下,已证明LOFDM系统误码性能优于正交频分复用(OFDM)系统。文章结合T urbo均衡技术和LOFDM系统提出了一种双扩散信道条件下拥有良好性能的T-LOFDM系统,并阐述了其工作原理。仿真实验表明:在双扩散信道条件下,T-LOFDM系统具有非常良好的性能,其误码率性能明显优于LOFDM结合MM SE均衡的系统,也明显优于OFDM结合T urbo均衡的系统。     

遥感数据处理任务调度的Petri网模型及求解算法

为了对多源遥感数据的处理任务进行有效的调度和管理,提高处理资源的利用率,根据遥感数据处理任务调度问题的特点,采用Petri网对该问题进行形式化描述,建立了遥感数据处理任务调度的数学模型,根据该问题的多目标特性,采用蚁群算法进行求解.给出仿真实例,将蚁群算法的求解结果与启发式算法和模拟退火算法的求解结果进行比较,验证算法...     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

面向计算流体力学的图形处理器资源管理

针对求解计算流体力学过程中图形处理器资源利用率低的问题,提出面向计算流体力学的图形处理器资源优化管理方案。基于计算流体力学的算法特性和同时运行任务的执行特点,设计合理的调度方案。通过动态改变不同任务的启动规模和启动时间,在减少资源竞争的同时提高图形处理器资源的有效使用。实验结果表明:本文提出的资源管理方案相比基线方法在不同任务规模下的平均加速比达到 1.64,对图形处理器的硬件资源使用也有了显著的提升。     

基于共进化的多任务分配与调度

在考虑多种约束关系基础上 ,提出一种并行与分布式系统中多约束关系的任务分配与调度的共同进化遗传算法。仿真试验结果表明所给算法比传统单种遗传算法更能有效地进行多任务分配与调度 ,具有一定的工程价值     

C2组织结构设计:平台-任务关系设计

以联合作战战役为例建立作战平台和任务模型,对C 2(Comm and and Con tro l)组织结构设计中平台-任务关系设计问题分析了传统多维动态列表规划算法(M u ltid im ens iona l D ynam ic L ist Schedu ling,M DLS)在解决作战平台资源调度(平台-任务分配)问题的不足,提出了在平台-任务分配过程中采用任务选择平台组、平台选择任务以及两者选择冲突消除改进的M DLS算法,以解决M DLS算法的不足,并对不同方法的结果进行了比较。     

联合作战规划中资源调度算法研究

以联合作战为例建立任务和作战平台资源模型,通过多维动态列表规划算法(M u ltid im ens iona l D ynam ic L istSchedu ling,M DLS)进行任务-平台分配,对平台选择提出了两种不同的优先权计算方法,通过对案例求解比较了不同方法的结果。     

面向两类典型分析仿真的多样本任务调度工具的设计

当在多台计算机上调度很多样本并行运行时,采用手工操作效率低且极易出错。设计一个自动化的任务分发与调度工具可以有效地提高仿真运行效率。蒙特卡罗仿真和粒子群优化算法仿真是两类典型的分析仿真,介绍了面向这两类仿真的多样本任务调度工具的实现原理和关键技术,这些方法具有很好的通用性和可扩展性,可以广泛应用于解决各类仿真任务的自动分发与调度问题。     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

分布式计算环境下的栅格数据存储策略

针对传统的栅格数据存储策略不能满足分布式计算环境下粗粒度数据访问需求,应对海量栅格数据计算时效率低下的问题,结合分布式文件系统的存储特点,同时考虑地图代数算子在Map/Reduce阶段以栅格瓦片为单位的计算特点,提出一种基于Hadoop分布式文件系统的栅格瓦片存储策略。围绕栅格数据瓦片分割、压缩瓦片数据组织与存储、分布式文件输入输出接口改进等方面对该存储策略加以实现,并使用基于该存储策略的地图代数局部算子的分布式计算流程加以验证。理论分析与实验结果表明,该策略能够显著提高分布式计算环境下空间分析算子的运算速度。