Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of ...Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed. MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data, thus it balances the number of spatial data in each partition. Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each parti- tion. Three area metrics are used to test the quality of generated index under different partitions. The extensive experiments show that the generated R-trees have the similar quality with the gener- ated R-tree using sequential bulk-loading method, while the execution time is reduced considerably by exploiting parallelism.展开更多
To decrease the cost of exchanging load information among processors, a dynamic load-balancing （DLB） algorithm which adopts multieast tree technology is proposed. The muhieast tree construction rules are also propos...To decrease the cost of exchanging load information among processors, a dynamic load-balancing （DLB） algorithm which adopts multieast tree technology is proposed. The muhieast tree construction rules are also proposed to avoid wrongly transferred or redundant DLB messages due to the overlapping of multicast trees. The proposed DLB algorithm is distributed controlled, sender initiated and can help heavily loaded processors with complete distribution of redundant loads with minimum number of executions. Experiments were executed to compare the effects of the proposed DLB algorithm and other three ones, the results prove the effectivity and practicability of the proposed algorithm in dealing with great scale compute-intensive tasks.展开更多
The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic l...The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic load balancing is a technique for the parallel implementation of problems, which generate unpredictable workloads by migration work units from heavily loaded processor to lightly loaded processors at run time. This paper proposed an efficient load balancing method in which parallel tree computations depth first search (DFS) generates unpredictable, highly imbalance workloads and moves through different phases detectable at run time, where dynamic load balancing strategy is applicable in each phase running under the MPI(message passing interface) and Unix operating system on cluster of workstations parallel platform computing.展开更多
The capacities of the nodes in the peer-to-peer system are strongly heterogeneous, hence one can benefit from distributing the load, based on the capacity of the nodes. At first a model is discussed to evaluate the lo...The capacities of the nodes in the peer-to-peer system are strongly heterogeneous, hence one can benefit from distributing the load, based on the capacity of the nodes. At first a model is discussed to evaluate the load balancing of the heterogeneous system, and then a novel load balancing scheme is proposed based on the concept of logical servers and the randomized binary tree, and theoretical guarantees are given. Finally, the feasibility of the scheme using extensive simulations is proven.展开更多
This paper presented an idea to replace the traditionally expensive parallel machines by heterogeneous cluster of workstations. To emphasise the usability of cluster of workstations platform for parallel and distribut...This paper presented an idea to replace the traditionally expensive parallel machines by heterogeneous cluster of workstations. To emphasise the usability of cluster of workstations platform for parallel and distributed computing, also the paper presented the status report on the effort and experiences for the implementation of a dynamic load balancing for parallel tree computation depth first search(DFS) on the cluster of a workstations project. It compared the speedup performance obtained from our platform with that obtained from the traditional one. The speedup results show that cluster of workstations can be a serious alternative to the expensive parallel machines.展开更多
The hex-cell is one of the interconnection networks used for parallel systems. The main idea of the hex-cell is that there are hexagon cells that construct the network;each one of those cells has six nodes. The perfor...The hex-cell is one of the interconnection networks used for parallel systems. The main idea of the hex-cell is that there are hexagon cells that construct the network;each one of those cells has six nodes. The performance of the network is affected by many factors one of the factors as load balancing. Until the moment of writing of this paper, there is no load balancing algorithm for this network. The proposed algorithm for dynamic load balancing on hex-cell is based on Tree Walking Algorithm (TWA) for load balancing on tree interconnection network and the ring all to all broadcast.展开更多
针对无线传感网络在实际应用中网络能耗不均匀、传感器节点容易失效以及网络生命周期短的问题,提出一种基于聚类树的负载平衡算法(load balancing algorithm based on cluster tree, LBACT)。基于聚类树将网络中的节点划分为多层结构,...针对无线传感网络在实际应用中网络能耗不均匀、传感器节点容易失效以及网络生命周期短的问题,提出一种基于聚类树的负载平衡算法(load balancing algorithm based on cluster tree, LBACT)。基于聚类树将网络中的节点划分为多层结构,通过立即转发机制降低聚类树的高度;使用平衡算法对构造的聚类树进行多轮次负载平衡,在汇聚节点的控制下,通过每个节点多次运行负载平衡算法,使网络中的节点负载平衡。仿真结果表明,相比LEACH(low-energy adaptive clustering hierarchy)和CBSHA(component based self-healing approach),提出的算法能够有效均衡节点能耗,延长网络的稳定期、生命周期,提高网络的吞吐量。展开更多
基金Supported by the National High Technology Research and Development Program of China (863 Program) (2011AA12A306)the National Natural Science Foundation of China (40801160,60902036)
文摘Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases. To solve this problem, a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed. MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data, thus it balances the number of spatial data in each partition. Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each parti- tion. Three area metrics are used to test the quality of generated index under different partitions. The extensive experiments show that the generated R-trees have the similar quality with the gener- ated R-tree using sequential bulk-loading method, while the execution time is reduced considerably by exploiting parallelism.
基金the National Natural Science Foundation of China(69973007)
文摘To decrease the cost of exchanging load information among processors, a dynamic load-balancing （DLB） algorithm which adopts multieast tree technology is proposed. The muhieast tree construction rules are also proposed to avoid wrongly transferred or redundant DLB messages due to the overlapping of multicast trees. The proposed DLB algorithm is distributed controlled, sender initiated and can help heavily loaded processors with complete distribution of redundant loads with minimum number of executions. Experiments were executed to compare the effects of the proposed DLB algorithm and other three ones, the results prove the effectivity and practicability of the proposed algorithm in dealing with great scale compute-intensive tasks.
基金Natural Science Foundation of China (No.60 173 0 3 1)
文摘The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic load balancing is a technique for the parallel implementation of problems, which generate unpredictable workloads by migration work units from heavily loaded processor to lightly loaded processors at run time. This paper proposed an efficient load balancing method in which parallel tree computations depth first search (DFS) generates unpredictable, highly imbalance workloads and moves through different phases detectable at run time, where dynamic load balancing strategy is applicable in each phase running under the MPI(message passing interface) and Unix operating system on cluster of workstations parallel platform computing.
基金the Electronic Development Foundation of Information Industry Ministry China (2002546).
文摘The capacities of the nodes in the peer-to-peer system are strongly heterogeneous, hence one can benefit from distributing the load, based on the capacity of the nodes. At first a model is discussed to evaluate the load balancing of the heterogeneous system, and then a novel load balancing scheme is proposed based on the concept of logical servers and the randomized binary tree, and theoretical guarantees are given. Finally, the feasibility of the scheme using extensive simulations is proven.
基金National Science Foundation of China(No.60 173 0 3 1)
文摘This paper presented an idea to replace the traditionally expensive parallel machines by heterogeneous cluster of workstations. To emphasise the usability of cluster of workstations platform for parallel and distributed computing, also the paper presented the status report on the effort and experiences for the implementation of a dynamic load balancing for parallel tree computation depth first search(DFS) on the cluster of a workstations project. It compared the speedup performance obtained from our platform with that obtained from the traditional one. The speedup results show that cluster of workstations can be a serious alternative to the expensive parallel machines.
文摘The hex-cell is one of the interconnection networks used for parallel systems. The main idea of the hex-cell is that there are hexagon cells that construct the network;each one of those cells has six nodes. The performance of the network is affected by many factors one of the factors as load balancing. Until the moment of writing of this paper, there is no load balancing algorithm for this network. The proposed algorithm for dynamic load balancing on hex-cell is based on Tree Walking Algorithm (TWA) for load balancing on tree interconnection network and the ring all to all broadcast.
文摘针对无线传感网络在实际应用中网络能耗不均匀、传感器节点容易失效以及网络生命周期短的问题,提出一种基于聚类树的负载平衡算法(load balancing algorithm based on cluster tree, LBACT)。基于聚类树将网络中的节点划分为多层结构,通过立即转发机制降低聚类树的高度;使用平衡算法对构造的聚类树进行多轮次负载平衡,在汇聚节点的控制下,通过每个节点多次运行负载平衡算法,使网络中的节点负载平衡。仿真结果表明,相比LEACH(low-energy adaptive clustering hierarchy)和CBSHA(component based self-healing approach),提出的算法能够有效均衡节点能耗,延长网络的稳定期、生命周期,提高网络的吞吐量。
