A Comparison of Implementation Strategies for Nonuniform Data-Parallel Computations

Data-parallel languages allow programmers to easily express parallel computations by means of high-level constructs. To reduce overheads, the compiler partitions the computations among the processors at compile-time, on the basis of the static data distribution suggested by the programmer. When execution costs are nonuniform and unpredictable, some processors may be assigned more work than others. Workload imbalance can be mitigated by cyclically distributing data and associated computations or by employing adaptive strategies which build a more balanced schedule at run-time, on the basis of the actual execution costs. This paper discusses static and hybrid (static+dynamic) scheduling strategies which can be used to balance the workloads derived from the execution of nonuniform parallel loops. A multidimensional flame simulation kernel has been used to evaluate different implementation strategies on a Cray T3E. We fed the benchmark code with synthetic input data sets built on the basis of a load imbalance model and we report and compare the results obtained.     

Processor preallocation and load balancing of DOALL loops

Load balance is important because it may affect the speedup attained through the concurrent execution of loop iterations on a parallel processor. We study loop load balance in the context of the well-known Perfect benchmarks. Several static and dynamic characteristics of the Perfect benchmark DOALL loops are observed and interpreted. Thelate arrival of processors is noted as a major source of load imbalance. This observation suggested the idea ofprocessor preallocation. An analytic cost model is presented and the advantages of processor preallocation are demonstrated by experimental evaluation on a CRAY Y-MP8 under the Unicos operating system.     

基于负荷平衡的电动汽车模糊多目标充电调度算法

居民小区电动汽车（EV）的单相充电方式导致配电网出现三相不平衡和负荷峰谷差问题,因此提出基于负荷平衡的EV模糊多目标充电调度策略。基于三相网络,将总延迟时间和充电平衡作为目标函数,考虑三相不平衡度和负荷峰谷差等约束,建立静态和在线调度问题下EV充电调度模型。采用改进非支配排序遗传算法-Ⅱ（NSGA-Ⅱ）进行多目标求解,通过设计交叉算子、自适应调整变异概率和局部优化等来优化结果。通过设置一定容量的外部档案和拥挤距离判定来获得Pareto最优前沿,并用模糊隶属度方法得到折中最优解。最后,通过算例分析可同时活动充电点和三相不平衡度的不同取值对优化结果的影响,并与无序充电进行比较,验证了所提模型和策略的有效性。     

一种针对线性循环结构的非线性静态调度策略

现有OpenMP调度策略通常采用动态策略处理程序中的线性循环结构,存在负载不均衡和调度开销大的问题。提出一种针对线性递增或线性递减循环结构的非线性静态调度策略Nonlinear_static。将线性循环负载均匀变化参数与总负载、负载峰值、线程数相结合构建调度模型,计算循环迭代在线程上的映射,使迭代块大小呈非线性递增或递减趋势。将线性循环的负载平均地分配在每个线程上,并在开源OMPi编译器中进行编码。在Adjoint Convolution、Compute Pots、Matrix Multiplication、Mandelbrot Set应用程序上进行多线程调度,实验结果表明,相比静态调度、动态调度、指导调度等策略,Nonlinear_static调度策略在处理线性循环结构时执行时间缩短了5%~10%,且具有无调度开销的优点。     

A Neurogenetic approach for the resource-constrained project scheduling problem

A variety of metaheuristic approaches have emerged in recent years for solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling. In this paper, we propose a Neurogenetic approach which is a hybrid of genetic algorithms (GA) and neural-network (NN) approaches. In this hybrid approach the search process relies on GA iterations for global search and on NN iterations for local search. The GA and NN search iterations are interleaved in a manner that allows NN to pick the best solution thus far from the GA pool and perform an intensification search in the solution's local neighborhood. Similarly, good solutions obtained by NN search are included in the GA population for further search using the GA iterations. Although both GA and NN approaches, independently give good solutions, we found that the hybrid approach gives better solutions than either approach independently for the same number of shared iterations. We demonstrate the effectiveness of this approach empirically on the standard benchmark problems of size J30, J60, J90 and J120 from PSPLIB.     

An experimental analysis of local minima to improve neighbourhood search

The paper reports the results from a number of experiments on local search algorithms applied to job shop scheduling problems. The main aim was to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e. the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.

Scope and purpose

The paper reports a number of experiments with local search algorithms applied to job shop scheduling (JSS). The JSS problem is defined as follows: Given a number of l jobs, the jobs have to be processed on m machines. Each job consists of a sequence of m tasks, i.e., each task of a job is assigned to a particular machine. The tasks have to be processed during an uninterrupted time period of a fixed length on a given machine. A schedule is an allocation of the tasks to time intervals on the machines and the aim is to find a schedule that minimises the overall completion time which is called the makespan. The scheduling problem is one of the hardest combinatorial optimization problems (cf. M.R. Garey, D.S. Johnson, SIAM J. Comput. 4(4) (1975) 397. Many methods have been proposed to find good approximations of optimum solutions to job shop scheduling problems; for an overview (see E.H.L. Aarts, Local Search in Combinatorial Optimization, Wiley, New York, 1998). In our paper, the main aim is to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e., the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.     

Distributed loop‐scheduling schemes for heterogeneous computer systems

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Some distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been designed in the past. In this work we study self‐scheduling schemes for parallel loops with independent iterations which have been applied to multiprocessor systems in the past. We extend one important scheme of this type to a distributed version suitable for heterogeneous distributed systems. We implement our new scheme on a network of computers and make performance comparisons with other existing schemes. Copyright © 2005 John Wiley & Sons, Ltd.     

数据驱动的多星任务网络预测调度算法

多星任务调度是具有NP-hard特性的优化问题,随着卫星资源规模和任务需求规模的双重增长,传统调度方法求解效率不高.在轨卫星在常年运行过程中积累了丰富的调度数据.针对大规模多星任务调度场景,建立多星多波束任务调度模型,并提出数据驱动的多星任务网络预测调度算法对其求解.以分割的思想,实现多星场景下任务可调度性预测.从历史调度数据中,提取设定的3个静态特征和5个动态特征,构建并训练预测网络,预测任务被不同卫星完成的概率,并以冲突避免、负载均衡等为原则,得到初始任务和资源卫星的分配方案.进一步设计双链结构的进化算法,以双链编码形式表征上述关系,配合设计的交叉、修复等进化算子,优化初始方案中的任务序列与资源分配关系,输出最终任务调度方案.仿真结果表明,与改进蚁群算法、混合遗传算法和数据驱动并行调度算法相比,所提出算法在运行时间、方案收益和卫星负载均衡3方面均有较好的表现.     

基于差分进化融合蚁群算法的数据中心流量调度机制

针对数据中心网络的传统流量调度方法容易引起网络拥塞及链路负载不均衡等问题,提出了一种差分进化（DE）融合蚁群（ACO）算法（DE-ACO）的动态流量调度机制,对数据中心网络中的大象流调度进行优化。首先,利用软件定义网络（SDN）技术捕获实时网络状态信息并设定流量调度的优化目标;然后,通过优化目标重定义DE算法,计算出多条可用候选路径,作为ACO算法的初始化全局信息素;最后,结合全局网络状态以求得全局最优路径,并重新路由拥堵链路上的大象流。实验结果表明,以在随机通信模式下为例,与等价多路径路由（ECMP）算法和基于蚁群算法的SDN数据中心网络流量调度（ACO-SDN）算法相比,所提算法的平均对分带宽分别提高了29.42%~36.26%和5%~11.51%,降低了网络的最大链路利用率（MLU）,较好地实现了网络负载均衡。     

基于安全策略的负载感知动态调度机制

针对软件定义网络（SDN）网络控制器流规则篡改攻击等单点脆弱性威胁,传统安全解决方案如备份、容错机制等存在被动防御缺陷,无法从根本上解决控制层安全问题。结合目前移动目标防御、网络空间拟态防御等主动防御技术研究现状,提出一种基于异构冗余结构的动态安全调度机制。建立控制器执行体与调度体调度模型,根据系统攻击异常、异构度等指标,以安全性为原则设计动态调度策略;同时考虑系统负载因素,通过设计调度算法LA-SSA将调度问题转化为动态双目标优化问题,以实现优化的调度方案。仿真结果表明,对比静态结构,动态调度机制在累积异常值、输出安全率等指标上有明显优势,说明安全调度机制中的动态性与多样性能够显著提高系统抵御攻击能力,LA-SSA机制负载方差较安全优先调度更平稳,在实现安全调度的同时避免了负载失衡问题,验证了安全调度机制的有效性。