Keywords: domain decomposition methods, heterogeneous cluster, load-balancing.

Domain decomposition methods and parallel computers are tightly connected. Domain decomposition algorithms are known for a long time but they were not used without computer aid because of computational complexity. Parallel computers create strongly and rapidly developing area which is still applied in more branches and disciplines. The first parallel computers were so-called massive because several processors were placed in one rack and were connected by special hardware. They are subsiding now because they are very expensive and other type of parallel computers has been originated--clusters. Clusters are created by several computers connected via computer network together. Computers creating cluster can be one or multi-processor machines and the communication is guaranteed by usual Ethernet. Clusters are cheap in comparison with massive parallel computers. The simple extension of clusters is also their big advantage. Clusters predominate massive parallel computers at this time and will prevail more clearly in the future.

Homogeneity or heterogeneity of parallel computer is very important property. Parallel computer is considered homogeneous if all processors are same, that means, they have same frequency, same RAM, same caches and so on. Otherwise, parallel computer is considered heterogeneous. The massive parallel machines are usually homogeneous but clusters are heterogeneous. This is caused by gradual construction of clusters, individual computers are involved at different times and newer ones are usually faster with larger RAM.

Domain decomposition methods are based on elimination of internal unknowns of subdomains and assembling reduced system where only boundary unknowns occur. Such reduced systems are solved iteratively or directly. It depends on size of the matrix of the reduced equation system. There are two basic classes of domain decomposition algorithms. The first class of methods works with original unknowns, the second one deals with dual variables.

Homogeneous parallel computers lead to regular decomposition of original domain into same subdomains. After such decomposition all processors have same amount of data and are assumed to perform same number of arithmetic operations. These facts result in good load-balancing. The situation is not so clear on heterogeneous machines because various processors are exploited. Decomposition of domain must be made with respect to ratios of processor efficiency. This is of course difficult because even the determination of processor efficiency ratios is not simple. Another problem arises from various numbers of elements and nodes on subdomains. Decomposition computer program is either relatively very complex or needs human assistance, which is undesirable. There are other conditions on decompositions arising from solution technique. As was mentioned above, decomposition methods create reduced system of equations where only boundary unknowns occur. It is clear that minimum number of boundary unknowns leads to good performance of algorithm. The same number of elements or nodes on subdomains is not enough for load-balancing because the profiles of the system matrices should be similar, ideally the same. It constitutes next conditions on decomposition strategy. Load-balancing of problems solved on heterogeneous computers is complicated task.

Several examples have been used for load-balancing investigation on heterogeneous cluster. Cluster is composed from 9 two-processor personal computers. The processor frequencies vary from 450 MHz to 1.19 GHz and RAM vary from 512 MB to 1 GB. It is shown irregular decomposition which leads to better result than regular one.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)