We generalize a result of Corrádi and Hajnal and show that every graph with average degree at least $\frac{4}{3}kr$ contains $k$ vertex disjoint cycles, each of order at least $r$, as long as $k \geq 6$. This bound is sharp when r=3.

Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq g(t)$ contains a $K_{t}$-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that $g(t) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (2+\epsilon)g(t)$, then we can find this $K_{t}$-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when $d(G) \geq 2^{t-2}$.

An important characteristic of distributed grids is that they allow geographically separated multicomputers to be tied together in a transparent virtual environment to solve large-scale computational problems. However, many of these applications require effective runtime load balancing for the resulting solutions to be viable. Recently, we developed a latency tolerant partitioner, called MinEX, specifically for use in distributed grid environments. We compare the performance of MinEX to that of METIS using simulated heterogeneous grid configurations. A solver for the classical N-body problem is implemented to provide a benchmark for the comparisons. Simulation results show that MinEX provides superior quality partitions while being competitive to METIS in speed of execution.

The Information Power Grid (IPG) concept developed by NASA is aimed to provide a metacomputing platform for large-scale distributed computations, by hiding the intricacies of a highly heterogeneous environment and yet maintaining adequate security. We propose a latency-tolerant partitioning scheme that dynamically balances processor workloads on the IPG, and minimizes data movement and runtime communication. By simulating an unsteady adaptive mesh application on a wide area network, we study the performance of our load balancer under the Globus environment. The number of IPG nodes, the number of processors per node, and the interconnect speeds are parameterized to derive conditions under which the IPG would be suitable for parallel distributed processing of such applications. Experimental results demonstrate that effective solutions are achieved when. The IPG nodes are connected by a high-speed asynchronous interconnection network.

NASA's Information Power Grid (IPG) is an infrastructure designed to harness the power of geographically distributed computers, databases and human expertise, in order to solve large-scale realistic computational problems. This type of a metacomputing environment is necessary to present a unified virtual machine to application developers that hides the intricacies of a highly heterogeneous environment and yet maintains adequate security. In this paper, we present a novel partitioning scheme, called MinEX, that dynamically balances processor workloads while minimizing data movement and runtime communication, for applications that are executed in a parallel distributed fashion on the IPG. Experimental results show that MinEX is an effective load balancer in a distributed IPG environment.

Many scientific applications involve grids that lack a uniform underlying structure. These applications are often also dynamic in nature in that the grid structure significantly changes between successive phases of execution. In parallel computing environments, mesh adaptation of unstructured grids through selective refinement/coarsening has proven to be an effective approach. However, achieving load balance while minimizing interprocessor communication and redistribution costs is a difficult problem. Traditional dynamic load balancers are mostly inadequate because they lack a global view of system loads across processors. In this paper, we propose a novel and general-purpose load balancer that utilizes symmetric broadcast networks (SBN) as the underlying communication topology and compare its performance with a successful global load balancing environment, called PLUM, specifically created to handle adaptive unstructured applications. Our experimental results on an IBM SP2 demonstrate that the SBN-based load balancer achieves lower redistribution costs than that under PLUM by overlapping processing and data migration.

Many scientific applications involve grids that lack a uniform underlying structure. These applications are often also dynamic in, nature in the sense that the grid structure significantly changes between successive phases of execution. In parallel computing environments, mesh adaptation of unstructured grids through selective refinement/coarsening has proven to be an effective approach. However, achieving load balance while minimizing interprocessor communication and redistribution costs is a difficult problem. Traditional dynamic load balancers are mostly inadequate because they lack a global view of system loads across processors. In this paper, we present a novel, general-purpose load balancer that utilizes symmetric broadcast networks (SBN) as the underlying communication topology. The experimental results on the IBM SP2 demonstrate that performance of the SBN-based load balancer is comparable to results achieved under PLUM, a global load balancing environment created to handle adaptive unstructured applications.

Article Free Access Share on Dynamic load balancing for adaptive meshes using symmetric broadcast networks Authors: Sajal K. Das Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile , Daniel J. Harvey Department of Computer Sciences, University of North Texas, Denton, TX Department of Computer Sciences, University of North Texas, Denton, TXView Profile , Rupak Biswas MRJ Technology Solutions, NASA Ames Research Center, Moffett Field, CA MRJ Technology Solutions, NASA Ames Research Center, Moffett Field, CAView Profile Authors Info & Claims ICS '98: Proceedings of the 12th international conference on SupercomputingJuly 1998 Pages 417–424https://doi.org/10.1145/277830.277934Published:13 July 1998Publication History 0citation321DownloadsMetricsTotal Citations0Total Downloads321Last 12 Months13Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In a distributed-computing environment, it is important to ensure that the processor work loads are adequately balanced. Among numerous load-balancing algorithms, a unique approach due to Das and Prasad defines a symmetric broadcast network (SBN) that provides a robust communication pattern among the processors in a topology-independent manner. In this paper, we propose and analyze three SBN-based load-balancing algorithms, and implement them on an SP2. A thorough experimental study with Poisson-distributed synthetic loads demonstrates that these algorithms are very effective in balancing system load while minimizing processor idle time. They also compare favorably with several existing techniques.