Skip Navigation

The Computer Journal 2005 48(3):300-314; doi:10.1093/comjnl/bxh086
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (4)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Dogan, A.
Right arrow Articles by Özgüner, F.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2005. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oupjournals.org

Biobjective Scheduling Algorithms for Execution Time–Reliability Trade-off in Heterogeneous Computing Systems*

Atakan Dogan1 § and Füsun Özgüner2 ¶

1 Department of Electrical and Electronics Engineering, Anadolu University, 26470 Eskisehir, Turkey, 2 Department of Electrical Engineering, The Ohio State University, 2015 Neil Avenue Columbus, OH 43210-1272, USA

A heterogeneous computing (HC) system is composed of a suite of geographically distributed high-performance machines interconnected by a high-speed network, thereby providing high-speed execution of computationally intensive applications with diverse demands. In HC systems, however, there is a possibility of machine and network failures and this can have an adverse impact on applications running on the system. In order to decrease the impact of failures on an application, matching and scheduling algorithms must be devised which minimize not only the execution time but also the failure probability of the application. However, because of the conflicting requirements, it is not possible to minimize both at the same time. Thus, the goal of this paper is to develop matching and scheduling algorithms which account for both the execution time and the failure probability and can trade off execution time against the failure probability of the application. In order to attain these goals, a biobjective scheduling problem is first formulated and then two different algorithms, the biobjective dynamic level scheduling algorithm and the biobjective genetic algorithm, are developed. Unique to both algorithms is the expression used for computing the failure probability of an application with precedence constraints. The simulation results confirm that the proposed algorithms can be used for producing task assignments where the execution time is weighed against the failure probability.

Received 10 April 2004. revised 12 November 2004.

* A preliminary version of this paper was published in 2001 International Parallel and Distributed Processing Symposium (IPDPS'01).

§ Email: atdogan{at}anadolu.edu.tr

Email: ozguner{at}ece.osu.edu


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.