東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Graph partitioning for parallel appl...

Kumar, Shailendra.

Linked to FindBook

Google Book

Amazon

博客來

Graph partitioning for parallel applications in heterogeneous grid environments.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Graph partitioning for parallel applications in heterogeneous grid environments./
Author:	Kumar, Shailendra.
Description:	68 p.
Notes:	Source: Masters Abstracts International, Volume: 40-06, page: 1548.
Contained By:	Masters Abstracts International40-06.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=1408932
ISBN:	0493632646

Graph partitioning for parallel applications in heterogeneous grid environments.
Kumar, Shailendra.

Graph partitioning for parallel applications in heterogeneous grid environments. - 68 p.

Source: Masters Abstracts International, Volume: 40-06, page: 1548.

Thesis (M.S.C.S.E.)--The University of Texas at Arlington, 2002.

The problem of partitioning irregular (unstructured) graphs and meshes for parallel computations on homogeneous systems has been extensively studied. However, these partitioning schemes fail when the target system architecture exhibits heterogeneity in resource characteristics. With the emergence of technologies such as the Grid, it is imperative to study the partitioning problem taking into consideration the differing capabilities of such distributed heterogeneous systems. In our model, the heterogeneous system consists of processors with varying processing power and an underlying non-uniform communication network. In this thesis, we present a novel multilevel partitioning scheme for irregular graphs and meshes, that takes into account issues pertinent to Grid computing environments. Our partitioning algorithm, called <italic> MiniMax</italic>, generates and maps partitions onto a heterogeneous system with the objective of minimizing the execution time of the parallel distributed applications. We have considered both a realistic mesh problem from NASA as well as synthetic workloads in order to study the performance of the proposed scheme, Experimental results demonstrate that MiniMax generates high quality partitions for a wide class of application types targeted for parallel execution in a distributed heterogeneous environment. Comparison of MiniMax with Metis (a popular homogeneous partitioner) shows that MiniMax outperforms Metis on the quality of partitions produced for a heterogeneous environment. For a non-uniform workload on a fully heterogeneous system, we obtain an improvement factor between 1.86 and 3.70 for execution time of the application, between 1.63 and 2.44 for load imbalance, and between 219 and 11487 for standard deviation among execution time of individual processors.

ISBN: 0493632646Subjects--Topical Terms:

626642
Computer Science.

Graph partitioning for parallel applications in heterogeneous grid environments.
LDR:02685nmm 2200265 4500 001 1810506
005 20040311141527.5
008 130610s2002 eng d
020 $a 0493632646
035 $a (UnM)AAI1408932
035 $a AAI1408932
040 $a UnM $c UnM
100 1 $a Kumar, Shailendra. $3 1900116
245 1 0 $a Graph partitioning for parallel applications in heterogeneous grid environments.
300 $a 68 p.
500 $a Source: Masters Abstracts International, Volume: 40-06, page: 1548.
500 $a Supervisor: Sajal K. Das.
502 $a Thesis (M.S.C.S.E.)--The University of Texas at Arlington, 2002.
520 $a The problem of partitioning irregular (unstructured) graphs and meshes for parallel computations on homogeneous systems has been extensively studied. However, these partitioning schemes fail when the target system architecture exhibits heterogeneity in resource characteristics. With the emergence of technologies such as the Grid, it is imperative to study the partitioning problem taking into consideration the differing capabilities of such distributed heterogeneous systems. In our model, the heterogeneous system consists of processors with varying processing power and an underlying non-uniform communication network. In this thesis, we present a novel multilevel partitioning scheme for irregular graphs and meshes, that takes into account issues pertinent to Grid computing environments. Our partitioning algorithm, called <italic> MiniMax</italic>, generates and maps partitions onto a heterogeneous system with the objective of minimizing the execution time of the parallel distributed applications. We have considered both a realistic mesh problem from NASA as well as synthetic workloads in order to study the performance of the proposed scheme, Experimental results demonstrate that MiniMax generates high quality partitions for a wide class of application types targeted for parallel execution in a distributed heterogeneous environment. Comparison of MiniMax with Metis (a popular homogeneous partitioner) shows that MiniMax outperforms Metis on the quality of partitions produced for a heterogeneous environment. For a non-uniform workload on a fully heterogeneous system, we obtain an improvement factor between 1.86 and 3.70 for execution time of the application, between 1.63 and 2.44 for load imbalance, and between 219 and 11487 for standard deviation among execution time of individual processors.
590 $a School code: 2502.
650 4 $a Computer Science. $3 626642
690 $a 0984
710 2 0 $a The University of Texas at Arlington. $3 1025869
773 0 $t Masters Abstracts International $g 40-06.
790 1 0 $a Das, Sajal K., $e advisor
790 $a 2502
791 $a M.S.C.S.E.
792 $a 2002
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=1408932