Task scheduling algorithm using minimized duplications in homogeneous systems

For fine grain task graphs, duplication-based scheduling algorithms are generally more efficient than list and cluster-based algorithms. However, most duplication-based heuristics try to duplicate all possible ancestor nodes of a given join node, in order to reduce the earliest start time (EST) of the join node, even though these ancestor nodes have already been allocated in previous steps. Thus, these duplication heuristics inevitably induce redundant duplications, which lead to the superfluous consumption of resources and generally deteriorate the scheduling result in the case of a bounded number of processors. When scheduling algorithms are used on an unbounded number of processors, the required number of processors grows excessively with the size of the task graph, thereby limiting the practicality of these algorithms for large task graphs. In this paper, we propose a novel algorithm designed to allocate join nodes without redundant duplications. In the proposed algorithm, if the ancestor nodes of a join node are duplicated when scheduling the join node, the original allocations of these ancestor nodes are removed using a very efficient method. The performance of the proposed algorithm, in terms of its normalized schedule length and efficiency, is compared with that of some of the recently proposed algorithms. The proposed algorithm generates better or comparable schedules with minimized duplication. Specifically, the simulation results show that it is most useful on a bounded number of processors.     

基于动态膜计算系统的自组织网络广播算法

应用仿生学原理设计了一种新型的广播算法——基于动态膜计算系统的广播算法,提出了动态膜计算系统,并给出了解决自组织网络中广播问题的规则集。系统中节点转播信息的优先权通过节点间距离及邻居个数确定,适合不同密度的网络;并根据信息数与门限值的比较,取消部分节点的转播权,从而提高了可达率和转播节省率。仿真测试验证了此系统用于广播是可行的、高效的,为设计无线自组织网络中的广播算法提供了新思路。     

一维高效动态负载平衡方法：多层均权法

提出了一个适合同构和异构并行计算环境的高效一维动态负载平衡方法;多层均权法,并成功地解决了多物质非定常流体力学Lagrange法并行数值模拟过程中的动态负载不平衡问题。文中给出了详细的理论分析以及两台并行机上结合某实际物理问题组织的并行数值实验。     

Identification of Optimal Set of Driver Nodes in Complex Networked Systems Using Region of Attraction

A controllable networked system is steered from an initial state to the desired state with the help of a set of driver nodes. The set of driver nodes used to control a networked system may not be unique. There exist multiple set of driver nodes which may be utilized to control the networked system. This is imperative to characterize these sets of driver nodes for identification of an optimal set of driver nodes. This paper presents mathematical formulation and two algorithms using the Region of Attraction (ROA) to identify an optimal set of driver nodes. Optimal set of driver nodes is identified to maximize the stability region. For any practical networked systems, driver node has limited actuating capacity, this paper consider this limitation a priori. The proposed mathematical formulation and algorithms are verified with the help of numerical examples using the MATLAB simulation. The proposed algorithms have been validated by applying on a robotic network.     

Wireless sensor network positioning based on the unilateral side of two reference nodes

We propose a new theory and method for unilateral positioning based on two reference nodes to reduce the number of reference nodes used in unilateral node deployment. In the method, a blind node obtains the location and distance of two reference nodes by establishing equations intended to derive two sets of solutions. The positioning solution of the blind node is then determined on the basis of one side of the line that connects the two reference nodes. To verify the accuracy of the new method, the proposed positioning theory is interpreted and simulated in a MATLAB environment. Results show that the highly accurate positioning generated by the proposed method is attributed to its basic principle and right method, thereby reducing the number of reference nodes needed for positioning in wireless sensor networks.     

Parallel iterative solvers for finite-element methods using an OpenMP/MPI hybrid programming model on the Earth Simulator

An efficient parallel iterative method for finite-element method has been developed for symmetric multiprocessor (SMP) cluster architectures with vector processors such as the Earth Simulator. The method is based on a three-level hybrid parallel programming model, including message passing for inter-SMP node communication, loop directives by OpenMP for intra-SMP node parallelization and vectorization for each processing element (PE). Simple 3D linear elastic problems with more than 2.2 × 10⁹ DOF have been solved using 3 × 3 block ICCG(0) method with additive Schwarz domain decomposition and PDJDS/CM-RCM reordering on 176 nodes of the Earth Simulator, achieving performance of 3.80 TFLOPS. Furthermore, effect of color number in reordering has been evaluated on various types of computers.     

Parallel branch and bound on fine-grained hypercube multiprocessors

In this paper, we study parallel branch and bound on fine grained hypercube multiprocessors. Each processor in a fine grained system has only a very small amount of memory available. Therefore, current parallel branch and bound methods for coarse grained systems ( 1000 nodes) cannot be applied, since all these methods assume that every processor stores the path from the node it is currently processing back to the node where the process was created (the back-up path). Furthermore, the much larger number of processors available in a fine grained system makes it imperative that global information (e.g. the current best solution) is continuously available at every processor; otherwise the amount of unnecessary search would become intolerable. We describe an efficient branch-and-bound algorithm for fine grained hypercube multiprocessors. Our method uses a global scheme where all processors collectively store all back-up paths such that each processor needs to store only a constant amount of information. At each iteration of the algorithm, all current nodes may decide whether they need to create new children, be pruned, or remain unchanged. We describe an algorithm that, based on these decisions, updates the current back-up paths and distributes global information in O(log m) steps, where m is the current number of nodes. This method also includes dynamic allocation of search processes to processors and provides optimal load balancing. Even if very drastic changes in the set of current nodes occur, our load balancing mechanism does not suffer any slow down.     

基于网络状态信息的车载网功率控制方法

针对车载自组网中,节点密度较高时,容易出现网络拥堵的情况,提出了一种动态调整消息发射功率的方法.通过信道忙闲比例(CBR)评估节点的网络状况,并在出现网络拥堵时泛洪广播拥堵信息,通知其他节点作出相应的功率调整.综合考虑功率覆盖范围和覆盖节点数两方面因素,设计了功率调整曲线.实验结果表明:方法能根据网络状况自适应地调整发射功率,降低了发生信道过载的可能性,并提高了信标消息传递的成功率.     

社交网络数据动态聚类调度算法实现

社交网络数据的庞大规模与复杂结构增加了目标数据获取难度,为此,提出一种社交网络数据动态聚类调度算法,根据节点密度值计算节点距离值,得到Z-score标准化后的密度-距离值,将标签分配给密度-距离较大值的对应节点,完成中心点识别,构建标签种子区域,按照降序密度-距离值更新标签,优先把标签分配至重要节点,实现社交网络数据的...     

Dynamic Load Balancing for Short-range Parallel Molecular Dynamics Simulations

The iterative Multilevel Averaging Weight (MAW) algorithm presented in paper [1] is modified to solve the dynamic load imbalance problems arising from the two-dimensional short-range parallel molecular dynamics simulations in this paper. Firstly, five types of load balancing models are given which allows detailed studies of the algorithm. In particular, it shows that for strip decomposition, the number of iteration needs for the system to converge from an initially unbalanced state to a well balanced state is bounded by 2 log P , where P is the number of processors. This result can permit the algorithm to efficiently track fluctuations in the molecular density as the simulation progresses, and is much better than that of the Cellular Automaton Diffusion (CAD) scheme presented in paper [2] . Secondly, we apply MAW algorithm to solve the load imbalance problem in the parallel molecular dynamics simulation for higher speed wall collisions. At last, the numerical experimental results and parallel computing performance with MPI-1.2 under a PC-Cluster consists of 64 Pentium-III 500 MHz nodes connected by 100 Mbps Switches are given in this paper.     

基于CPLD和多处理器结构的控制网络节点设计

节点是控制网络系统的基本构成单元。论文提出了一种基于CPLD和多处理器结构的控制网络节点设计方法。它能够提高单节点的并行处理能力,其模块化结构增强了节点的可靠性;不同处理器之间的连接形式可以通过VHDL等软件在线改变,使得节点柔性与扩展性提高。同时,其软件可按照不同处理器模块分步开发,软件结构也得以简化,有利于节点的调试。遵循该方法,成功开发出一种多功能LonWorks控制网络节点。     

基于改进模拟植物生长算法的配电网重构

针对模拟植物生长算法所存在的需遍历搜索区域进行寻优导致计算量太大的问题。将支路交换算法中所用的启发式交换规则与之相结合。提出一种用于配电网重构的改进模拟植物生长算法。所提方法的主要优点,是在保留模拟植物生长算法所具备的全局寻优能力的同时,大大减少每一步计算中所产生的生长点集的数量,因而减少相应的潮流计算、目标函数值计算及形态素浓度计算的次数即计算量．对IEEE33节点系统的计算结果,验证所提方法的有效性。     

A robustness measure for hypercube networks

Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (B_n) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In B_n, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in B_n, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in B_n. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%.     

融入迁移限制与双层集合种群网络的传染病模型

本文在斑块环境下基于易感–感染–易感模型(SIS模型)研究了感染者迁移限制对传染病传播的影响,其中迁移限制用双层网络进行表示,并提出了双层集合种群动态网络.子种群(即斑块)用双层网络上的节点表示,双层网络上的链接分别代表易感节点斑块和感染节点斑块间的迁移路径,易感染和感染节点分别通过双层网络上的链接随机游走.并提出了两种反应扩散方程分别作为易感染与感染节点的微分方程,分别计算其数值解,以评估每个斑块(节点)的感染风险.研究表明:在双层网络中,迁移限制会降低感染节点密度,将感染节点限制在中心节点(度值最高的子种群)中.感染节点密度高度依赖于双层网络结构.     

The approximate Dirichlet Domain Decomposition method. Part I: An algebraic approach

We present a new approach to the construction of Domain Decomposition (DD) preconditioners for the conjugate gradient method applied to the solution of symmetric and positive definite finite element equations. The DD technique is based on a non-overlapping decomposition of the domain Ω intop subdomains connected later with thep processors of a MIMD computer. The DD preconditioner derived contains three block matrices which must be specified for the specific problem considered. One of the matrices is used for the transformation of the nodal finite element basis into the approximate discrete harmonic basis. The other two matrices are block preconditioners for the Dirichlet problems arising on the subdomains and for a modified Schur complement defined over all nodes on the coupling boundaries between the subdomains. The relative spectral condition number is estimated. Relations to the additive Schwarz method are discussed. In the second part of this paper, we will apply the results of this paper to two-dimensional, symmetric, second-order, elliptic boundary value problems and present numerical results performed on a transputer-network.     

基于水平集的围猎式水下传感器节点布置研究

水下传感器网络作为一种探索和开发海洋的新方法,在人类不易接触的水下区域的探测和监测中发挥着重要作用,是无线传感器网络领域研究的热点.在水下空间中传感器节点如何自主调整位置实现对"兴趣域"的覆盖和监视是一个重要课题.该文引入水平集理论LSM,提出了一种基于水平集的围猎式水下传感器节点布置方法.在该方法中网关节点根据传感器...     

Dynamic critical-path scheduling: an effective technique forallocating task graphs to multiprocessors

In this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures     

基于H运算的动态网络重要节点识别方法

传统K-shell网络重要节点识别方法迭代时需网络全局拓扑信息,而且难以应用于动态网络。为解决该问题,提出基于邻域优先异步H运算的动态网络重要节点识别方法。首先,证明该算法收敛于Ks值,其次以各节点的度作为h指数初始值;然后,通过节点h指数排序和邻居节点h指数变化选择更新节点,同时针对动态网络节点的增减数目和最大度,修改h指数适应拓扑变化,直至算法收敛并找到重要节点。仿真实验结果表明,该方法通过邻居节点局部信息且以更高效率找到动态网络的重要节点,收敛时间在静态网络中较随机选择更新节点法与变化邻居选点法分别下降77.4%和28.3%,在网络拓扑变化后分别下降84.3%和38.8%。     

LAI：一种基于连通度的无线传感器网络节点定位算法

无线传感器网络的节点定位算法中,LCO算法将节点间具有连通度的通信连接视为对节点位置的约束,并由此确定节点的位置估计.提出了一种改进的分布式节点定位算法LAI(Localization with All Nodes and Iteration),结合不具有连通度的节点位置关系进行定位.仿真实验结果表明,改进算法相对于LCO算法,提高了定位估计的准确性,减小了对于锚节点的依赖程度.     

基于均衡分簇的无线传感器网络压缩数据收集

应用压缩感知（CS）理论结合稀疏随机投影的无线传感器网络（WSN）压缩数据收集（CDG）可以大大减少网络传输的数据量。针对随机选择投影节点作为簇头来收集数据导致网络整体能耗不稳定和不平衡的问题,提出两种平衡投影节点的压缩数据收集方法。对于节点分布均匀WSN,提出基于空间位置的均衡分簇法：首先,均匀划分网格;然后,在每个网格选举投影节点,依距离最短原则成簇;最后,由投影节点收集簇内数据到汇聚节点完成数据收集,从而使得投影节点分布均匀、网络能耗均衡。对于节点分布不均匀的WSN,提出基于节点密度的均衡分簇法：同时考虑节点的位置和密度,对节点数量少的网格不再选择投影节点,将网格内的少量节点分配到邻近的网格,从而平衡网络能量,延长网络寿命。仿真结果表明,与随机投影节点法相比,所提的两种方法的网络寿命均延长了25%以上,剩余节点数在网络运行中期均能达到2倍左右,具有更好的网络连通性,显著提高了整个网络的生命周期。