Open Access System for Information Sharing

Login Library

 

Article
Cited 4 time in webofscience Cited 0 time in scopus
Metadata Downloads

Task scheduling using a block dependency DAG for block-oriented sparse Cholesky factorization

Title
Task scheduling using a block dependency DAG for block-oriented sparse Cholesky factorization
Authors
Lee, HKim, JHong, SJLee, S
POSTECH Authors
Kim, JLee, S
Date Issued
Jan-2003
Publisher
ELSEVIER SCIENCE BV
Abstract
Block-oriented sparse Cholesky factorization decomposes a sparse matrix into rectangular subblocks
each block can then be handled as a computational unit in order to increase data reuse in a hierarchical memory system. Also, the factorization method increases the degree of concurrency and reduces the overall communication volume so that it performs more efficiently on a distributed-memory multiprocessor system than the customary column-oriented factorization method. But until now, mapping of blocks to processors has been designed for load balance with restricted communication patterns. In this paper, we represent tasks using a block dependency DAG that represents the execution behavior of block sparse Cholesky factorization in a distributed-memory system. Since the characteristics of tasks for block Cholesky factorization are different from those of the conventional parallel task model, we propose a new task scheduling algorithm using a block dependency DAG. The proposed algorithm consists of two stages: early-start clustering, and affined cluster mapping (ACM). The early-start clustering stage is used to cluster tasks while preserving the earliest start time of a task without limiting parallelism. After task clustering, the ACM stage allocates clusters to processors considering both communication cost and load balance. Experimental results on Myrinet cluster system show that the proposed task scheduling approach outperforms other processor mapping methods. (C) 2002 Elsevier Science B.V. All rights reserved.
Keywords
task scheduling; parallel sparse matrix factorization; block-oriented Cholesky factorization; directed acyclic graph; MEMORY MULTIPROCESSOR; PARALLEL ALGORITHMS; LINEAR-SYSTEMS; GRAPHS; COMMUNICATION; ARCHITECTURES
URI
http://oasis.postech.ac.kr/handle/2014.oak/18690
ISSN
0167-8191
Article Type
Article
Citation
PARALLEL COMPUTING, vol. 29, no. 1, page. 135 - 159, 2003-01
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 LEE, SUNG GU
Dept of Electrical Enginrg
Read more

Views & Downloads

Browse