共查询到20条相似文献,搜索用时 0 毫秒
1.
Ahmad I. Ghafoor A. 《IEEE transactions on pattern analysis and machine intelligence》1991,17(10):987-1004
A semidistributed approach is given for load balancing in large parallel and distributed systems which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. The authors consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and, using their algebraic characteristics, show that identification of spheres and their scheduling points is in general an NP-complete problem. An efficient solution for this problem is presented by making exclusive use of a combinatorial structure known as the Hadamard matrix. The performance of the proposed strategy has been evaluated and compared with an efficient fully distributed strategy through an extensive simulation study. The proposed strategy yielded much better results 相似文献
2.
Satish PenmatsaAuthor Vitae Anthony T. ChronopoulosAuthor Vitae 《Journal of Parallel and Distributed Computing》2011,71(4):537-555
In this paper, we present a game theoretic approach to solve the static load balancing problem for single-class and multi-class (multi-user) jobs in a distributed system where the computers are connected by a communication network. The objective of our approach is to provide fairness to all the jobs (in a single-class system) and the users of the jobs (in a multi-user system). To provide fairness to all the jobs in the system, we use a cooperative game to model the load balancing problem. Our solution is based on the Nash Bargaining Solution (NBS) which provides a Pareto optimal solution for the distributed system and is also a fair solution. An algorithm for computing the NBS is derived for the proposed cooperative load balancing game. To provide fairness to all the users in the system, the load balancing problem is formulated as a non-cooperative game among the users who try to minimize the expected response time of their own jobs. We use the concept of Nash equilibrium as the solution of our non-cooperative game and derive a distributed algorithm for computing it. Our schemes are compared with other existing schemes using simulations with various system loads and configurations. We show that our schemes perform near the system optimal schemes and are superior to the other schemes in terms of fairness. 相似文献
3.
Dynamic load balancing on Web-server systems 总被引:1,自引:0,他引:1
Popular Web sites cannot rely on a single powerful server nor on independent mirrored-servers to support the ever-increasing request load. Distributed Web server architectures that transparently schedule client requests offer a way to meet dynamic scalability and availability requirements. The authors review the state of the art in load balancing techniques on distributed Web-server systems, and analyze the efficiencies and limitations of the various approaches 相似文献
4.
Adaptive mesh refinement (AMR) is a type of multiscale algorithm that achieves high resolution in localized regions of dynamic, multidimensional numerical simulations. One of the key issues related to AMR is dynamic load balancing (DLB), which allows large-scale adaptive applications to run efficiently on parallel systems. In this paper, we present an efficient DLB scheme for structured AMR (SAMR) applications. This scheme interleaves a grid-splitting technique with direct grid movements (e.g., direct movement from an overloaded processor to an underloaded processor), for which the objective is to efficiently redistribute workload among all the processors so as to reduce the parallel execution time. The potential benefits of our DLB scheme are examined by incorporating our techniques into a SAMR cosmology application, the ENZO code. Experiments show that by using our scheme, the parallel execution time can be reduced by up to 57% and the quality of load balancing can be improved by a factor of six, as compared to the original DLB scheme used in ENZO. 相似文献
5.
Didier Y. Hinz 《Acta Informatica》1992,29(1):63-94
We discuss a simple run-time load balancing strategy which applies to numerical applications working on planar domains with localized data dependency. We develop an iterative and adaptive partitioner, able to work in a distributed way among the processors of a parallel system. Our algorithm subdivides data space into general quadrilaterals, where each processor works on the data of one area. The topology of these domains is that of a rectangular grid and does not change during execution. In this way a very simple and efficient communication structure is given. The administration overhead due to irregular geometry is small. Also, the overhead caused by periodically read-justing load balance is rather small because of the adaptivity and parallelity of the partitioning algorithm. We ran an scientific application to compare our method with a method working by recursive bisection, and obtained satisfactory results. 相似文献
6.
Grosu D. Chronopoulos A.T. 《IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics》2004,34(1):77-84
Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mechanism design theory. Using this theory, we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness. 相似文献
7.
Alejandro Acosta Vicente BlancoAuthor VitaeFrancisco AlmeidaAuthor Vitae 《Computers & Electrical Engineering》2013
Actual HPC systems are composed by multicore processors and powerful graphics processing units. Adapting existing code and libraries to these new systems is a fundamental problem due to the important increment on programming difficulties. The heterogeneity, both at architectural and programming levels at the same time, raises the programmability wall. The performance of the code is affected by the large interdependence between the code and the parallel architecture. We have developed a dynamic load balancing library that allows parallel code to be adapted to a wide variety of heterogeneous systems. The overhead introduced by our system is minimal and the cost to the programmer negligible. This system has been successfully applied to solve load imbalance problems appearing in homogeneous and heterogeneous multiGPU platforms. We consider the Dynamic Programming technique as case of study to validate our proposals using different heterogeneous scenarios in multiGPU systems. 相似文献
8.
Ioannis Riakiotakis Florina M. Ciorba Theodore Andronikos George Papakonstantinou 《Parallel Computing》2011,37(10-11):713-729
One of the most significant causes for performance degradation of scientific and engineering applications on high performance computing systems is the uneven distribution of the computational work to the resources of the system. This effect, which is known as load imbalance, is even more noticeable in the case of irregular applications and heterogeneous distributed systems. This motivated the parallel and distributed computing research community to focus on methods that provide good load balancing for scientific and engineering applications running on (heterogeneous) distributed systems. Efficient load balancing and scheduling methods are employed for scientific applications from various fields, such as mechanics, materials, physics, chemistry, biology, applied mathematics, etc. Such applications typically employ a large number of computational methods in order to simulate complex phenomena, on very large scales of time and magnitude. These simulations consist of routines that perform repetitive computations (in the form of DO/FOR loops) over very large data sets, which, if not properly implemented and executed, may suffer from poor performance. The number of repetitive computations in the simulation codes is not always constant. Moreover, the computational nature of these simulations may be in fact irregular, leading to the case when one computation takes (unpredictably) more time than others. For successful and timely results, large scale simulations require the use of large scale computing systems, which often are widely distributed and highly heterogeneous. Moreover, large scale computing systems are usually shared among multiple users, which causes the quality and quantity of the available resources to be highly unpredictable. There are numerous load balancing methods in the literature for different parallel architectures. The most recent of these methods typically follow the master-worker paradigm, where a single coordinator (master) is responsible for making all the scheduling decisions based on information provided by the workers. Depending on the application requirements, the scheduling policy and the computational environment, the benefits of this paradigm may be limited as follows: (1) its efficiency may not scale as the number of processors increases, and (2) it is quite probable that the scheduling decisions are made based on outdated information, especially on systems where the workload changes rapidly. In an effort to address these limitations, we propose a distributed (master-less) load balancing scheme, in which the scheduling decisions are made by the workers in a distributed fashion. We implemented this method along with other two master-worker schemes (a previously existing one and a recently modified one) for three different scientific computational kernels. In order to validate the usefulness and efficiency of the proposed scheme, we conducted a series of comparative performance tests with the two master-worker schemes for each computational kernel. The target system is an SMP cluster, on which we simulated three different patterns of system load fluctuation. The experiments strongly support the belief that the distributed approach offers greater performance and better scalability on such systems, showing an overall improvement ranging from 13% to 24% over the master-worker approaches. 相似文献
9.
F. Farahnakian M. Ebrahimi M. Daneshtalab P. Liljeberg J. Plosila 《The Journal of supercomputing》2014,68(3):1214-1234
Adaptive routing algorithms improve network performance by distributing traffic over the whole network. However, they require congestion information to facilitate load balancing. To provide local and global congestion information, we propose a learning method based on dual reinforcement learning approach. This information can be dynamically updated according to the changing traffic condition in the network by propagating data and learning packets. We utilize a congestion detection method which updates the learning rate according to the congestion level. This method calculates the average number of free buffer slots in each switch at specific time intervals and compares it with maximum and minimum values. Based on the comparison result, the learning rate sets to a value between 0 and 1. If a switch gets congested, the learning rate is set to a high value, meaning that the global information is more important than local. In contrast, local is more emphasized than global information in non-congested switches. Results show that the proposed approach achieves a significant performance improvement over the traditional Q-routing, DRQ-routing, DBAR and Dynamic XY algorithms. 相似文献
10.
Contemporary operating systems for single-ISA (instruction set architecture) multi-core systems attempt to distribute tasks equally among all the CPUs. This approach works relatively well when there is no difference in CPU capability. However, there are cases in which CPU capability differs from one another. For instance, static capability asymmetry results from the advent of new asymmetric hardware, and dynamic capability asymmetry comes from the operating system (OS) outside noise caused from networking or I/O handling. These asymmetries can make it hard for the OS scheduler to evenly distribute the tasks, resulting in less efficient load balancing. In this paper, we propose a user-level load balancer for parallel applications, called the ’capability balancer’, which recognizes the difference of CPU capability and makes subtasks share the entire CPU capability fairly. The balancer can coexist with the existing kernel-level load balancer without detrimenting the behavior of the kernel balancer. The capability balancer can fairly distribute CPU capability to tasks with very little overhead. For real workloads like the NAS Parallel Benchmark (NPB), we have accomplished speedups of up to 9.8% and 8.5% in dynamic and static asymmetries, respectively. We have also experienced speedups of 13.3% for dynamic asymmetry and 24.1% for static asymmetry in a competitive environment. The impacts of our task selection policies, FIFO (first in, first out) and cache, were compared. The use of the cache policy led to a speedup of 5.3% in overall execution time and a decrease of 4.7% in the overall cache miss count, compared with the FIFO policy, which is used by default. 相似文献
11.
Many solutions have been proposed to tackle the load balancing issue in DHT-based P2P systems. However, all these solutions either ignore the heterogeneity nature of the system, or reassign loads among nodes without considering proximity relationships, or both. In this paper, we present an efficient, proximity-aware load balancing scheme by using the concept of virtual servers. To the best of our knowledge, this is the first work to use proximity information in load balancing. In particular, our main contributions are: 1) relying on a self-organized, fully distributed k-ary tree structure constructed on top of a DHT, load balance is achieved by aligning those two skews in load distribution and node capacity inherent in P2P systems - that is, have higher capacity nodes carry more loads; 2) proximity information is used to guide virtual server reassignments such that virtual servers are reassigned and transferred between physically close heavily loaded nodes and lightly loaded nodes, thereby minimizing the load movement cost and allowing load balancing to perform efficiently; and 3) our simulations show that our proximity-aware load balancing scheme reduces the load movement cost by 11-65 percent for all the combinations of two representative network topologies, two node capacity profiles, and two load distributions of virtual servers. Moreover, we achieve virtual server reassignments in O(log N) time. 相似文献
12.
Hua K.A. Chiang Lee Hua C.M. 《Knowledge and Data Engineering, IEEE Transactions on》1995,7(6):968-983
Shared nothing multiprocessor architecture is known to be more scalable to support very large databases. Compared to other join strategies, a hash-based join algorithm is particularly efficient and easily parallelized for this computation model. However, this hardware structure is very sensitive to the skew in tuple distribution. Unless the parallel hash join algorithm includes some dynamic load balancing mechanism, the skew effect can severely deteriorate the system performance. In this paper, we investigate this issue. In particular, three parallel hash join algorithms are presented. We implement a simulator to study the effectiveness of these schemes. The simulation model is validated by comparing the simulation results to those produced by the actual implementation of the algorithms running on a multiprocessor system. Our performance study indicates that a naive approach is not able to provide tangible savings. However, the carefully designed strategies can offer substantial improvement over conventional techniques for a wide range of skew conditions 相似文献
13.
Toktam Ghafarian Hossein Deldari Bahman Javadi Rajkumar Buyya 《The Journal of supercomputing》2013,65(2):797-822
One of the main challenges in peer-to-peer-based volunteer computing systems is an efficient resource discovery algorithm. Load balancing is a part of resource discovery algorithm and aims to minimize the overall response time of the system. This paper introduces an analytical model based on distributed parallel queues to optimize the average response time of the system in a distributed manner. The proposed resource discovery algorithm consists of two phases. In the first phase, it selects peers in a load-balanced manner based on QoS constraints of request. In the second phase, a proximity-aware feature is applied to select the peer with minimum communication overhead among selected peers in the first phase. Two dispatching strategies are proposed for the load balancing based on stochastic analysis of routing in the distributed parallel queues. These policies adopt probabilistic and deterministic sequences to redirect requests to the capable peers in the system. Simulation results show that the proposed resource discovery algorithm improves the response time of user’s requests by a factor of 1.8 under a moderate load. 相似文献
14.
Since the 802.16e standard has been released, there are few authentication pattern schemes and Extensible Authentication Protocol (EAP) selection proposals for manufacturers to choose from in large-scale network systems. This paper focuses on the re-authentication method??s design, improvement, and optimization for the PMP mode of the IEEE 802.16e standard in large-scale network systems to ensure the security of the keys. We first present an optimized scheme, called EAP_AKAY, based on the EAP-AKA authentication method (Arkko and Haverinen in Extensible Authentication Protocol Method for UMTS Authentication and Key Agreement (EAP-AKA), 2004), and then a self-adaptive K selection mechanism is proposed for re-authentication load balancing based on EAP_AKAY in large-scale network systems. This presented mechanism considers the cost of authentication, not only at the server end, but also at the client end. Thus, this scheme would minimize the total cost and resolve the limitation in current schemes. Furthermore, the K value would be re-selected, not only when MS is roaming to another BS region, but also in residing time to adapt to network environment changes. The simulation results and relevant analysis demonstrate that our scheme is effective in terms of the total cost of authentication, master key renewal, and good security. 相似文献
15.
Yasutaka Takeda Hiroshi Nakashima Kanae Masuda Takashi Chikayama Kazuo Taki 《New Generation Computing》1990,7(2-3):179-195
In large scale multiprocessor systems, the distance between processors should be taken into account by software to reduce the network traffic and the communication overhead. A load balancing method based on P3 (Processing Power Plane) model is proposed to enable programmers to specify distributing computational load, keeping the locality of the computation. In this method, a process is allocated to a rectangle on a hypothetical processing power plane. The size of the rectangle represents the processing power given to the process, and the distance between rectangles represents the communication cost between them. This plane is divided to processors, and the region of the processor may be dynamically reshaped to alleviate imbalance on P3. Mechanism for realization of the method has been implemented on the Multi-PSI/version, 2, which is a parallel processing system with 64 processing elements connected to form a 2-dimensional mesh network. A packet transmission mechanism of the Multi-PSI/version 2 is described, which realizes the process distribution along with the balancing method. 相似文献
16.
Dynamic file grouping for load balancing in streaming media clustered server systems 总被引:1,自引:0,他引:1
Qi Jiang Hong-Sheng Xi Bao-Qun Yin 《International Journal of Control, Automation and Systems》2009,7(4):630-637
A dynamic file grouping strategy is presented to address the load balancing problem in streaming media clustered server systems.
This strategy increases the server cluster availability by balancing the workloads among the servers within a cluster. Additionally,
it improves the access hit ratio of cached files in delivery servers to alleviate the limitation of I/O bandwidth of storage
node. First, the load balancing problem is formulated as a two layers semi-Markov switching state-space control process. This
analytic model captures the behaviors of streaming media clustered server systems accurately, and is with constructional flexibility
and scalability. Then, a policy iteration based reinforcement learning algorithm is proposed to optimize the file grouping
policy online. By utilizing the features of the event-driven policy, the proposed optimization algorithm is adaptive and with
less computational cost. Simulation results demonstrate the effectiveness of the proposed approach.
Recommended by Editor Hyun Seok Yang. This work was supported by the National Natural Science Foundation of China under grant
Nos. 60774038, 60574065, National 863 HI-TECH Research & Development Plan of China under grant Nos. 2006AA01Z114, 2008AA01A317,
Natural Science Foundation of Anhui Province under grant No. 070412063, Graduate Student Innovation Foundation of USTC under
grant No. KD2006036, and Science Research Development Foundation of HFUT under grant No. GDBJ2008-045.
Qi Jiang received the B.S. degree in Industrial Electrical Automation from Southeast University in 1989 and the Ph.D. degree in Control
Science and Engineering from University of Science and Technology of China in 2008. He is currently a Post-doc in USTC. His
research interests include optimization and control of stochastic dynamic systems, and performance analysis and optimization
of network communication systems.
Hong-Sheng Xi received the M.S. degree in Applied Mathematics from University of Science and Technology of China in 1977. He is currently
a Professor in Department of Automation, USTC. His research interests include discrete event dynamic systems, performance
analysis and optimization of network communication systems, robust control, and network security.
Bao-Qun Yin received the B.S. degree in Mathematics from Sichuan University in 1985, the M.S. degree in Applied Mathematics and the Ph.D.
degree in Pattern Recognition and Intelligent Systems from University of Science and Technology of China in 1993 and 1998,
respectively. He is currently a Professor in Department of Automation, USTC. His research interests include discrete event
dynamic systems, and Markov decision processes. 相似文献
17.
Hydrodynamic load balancing 总被引:1,自引:0,他引:1
Chi-Chung Hui Chanson S.T. 《Parallel and Distributed Systems, IEEE Transactions on》1999,10(11):1118-1137
This paper presents a hydrodynamic framework to solving the dynamic load balancing problem in heterogeneous distributed systems. In this approach, each processor is viewed as a liquid cylinder where the cross-sectional area corresponds to the capacity of the processor, the communication links are modeled as liquid channels between the cylinders, the workload is represented by liquid, and the load balancing algorithm manages the flow of the liquid. It is proven that all algorithms under this framework converge geometrically to the state of equilibrium, in which the heights of the liquid columns are the same in all the cylinders. In this way, each processor obtains an amount of workload proportional to its capacity. A hydrodynamic algorithm is presented and its performance is evaluated. The algorithm is applied to solve several practical applications to demonstrate the applicability of the framework 相似文献
18.
基于P2P系统的动态负载均衡算法 总被引:1,自引:0,他引:1
在现实的P2P网络环境中,由于节点的计算能力和带宽等方面的异构性,网络负载不均衡现象非常突出.基于数据复制/转移策略,提出一种动态的平衡算法.根据节点的能力,当前节点负载状态、负载转移代价预估算,在整个系统范围内找到一组传输代价较小并且负载较轻的节点集合,从中随机选取较为适宜的节点进行负载转移或者数据复制.试验结果表明,该算法能够有效地均衡负载的分布以及降低负载的迁移率. 相似文献
19.
Colin Kristen N. Paul E. Sascha A. Maria Nikolaos P. 《Robotics and Autonomous Systems》2003,44(3-4):251-7
This paper describes the latest advances made to a software architecture designed to control multiple miniature robots. As the robots themselves have very limited computational capabilities, a distributed control system is needed to coordinate tasks among a large number of robots. Two of the major challenges facing such a system are the scheduling of access to system resources and the distribution of work across multiple workstations. This paper discusses solutions to these problems in the context of a distributed surveillance task. 相似文献
20.
一种动态的入侵检测系统负载均衡算法 总被引:2,自引:0,他引:2
目前的入侵检测不仅需要模式匹配,而且需要协议异常检测,提出了一种新动态的负载均衡算法,采用两层结构,对网络流量按照服务类型进行初步划分之后分别对每部分流量进行二次分配,并对每种类型的流量进行相应的协议异常检测。该算法能在不牺牲系统性能的前提下有效提高网络入侵检测系统的检测效率,降低误检率,并可有效地适应网络流量的变化,降低漏检率。 相似文献