File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A semi-static approach to mapping dynamic iterative tasks onto heterogeneous computing systems

TitleA semi-static approach to mapping dynamic iterative tasks onto heterogeneous computing systems
Authors
KeywordsAutomatic target recognition
Genetic algorithms
Heterogeneous computing
Iterative task graphs
Mapping
Parallel processing
Scheduling
Issue Date2006
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdc
Citation
Journal Of Parallel And Distributed Computing, 2006, v. 66 n. 1, p. 77-98 How to Cite?
AbstractMinimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the "best" mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations. © 2005 Elsevier Inc. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/73864
ISSN
2015 Impact Factor: 1.32
2015 SCImago Journal Rankings: 0.851
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorMacIejewski, AAen_HK
dc.contributor.authorSiegel, HJen_HK
dc.contributor.authorAhmad, Ien_HK
dc.contributor.authorGhafoor, Aen_HK
dc.date.accessioned2010-09-06T06:55:30Z-
dc.date.available2010-09-06T06:55:30Z-
dc.date.issued2006en_HK
dc.identifier.citationJournal Of Parallel And Distributed Computing, 2006, v. 66 n. 1, p. 77-98en_HK
dc.identifier.issn0743-7315en_HK
dc.identifier.urihttp://hdl.handle.net/10722/73864-
dc.description.abstractMinimization of the execution time of an iterative application in a heterogeneous parallel computing environment requires an appropriate mapping scheme for matching and scheduling the subtasks of a given application onto the processors. Often, some of the characteristics of the application subtasks are unknown a priori or change from iteration to iteration during execution-time based on the inputs being processed. In such a scenario, it may not be feasible to use the same off-line-derived mapping for each iteration of the application. One possibility is to employ a semi-static methodology that starts with an initial mapping but dynamically performs remapping between application iterations by observing the effects of the changing characteristics of the application's input data, called dynamic parameters, on the application's execution time. A contribution in this paper is to implement and evaluate a semi-static methodology involving the on-line use of off-line-derived mappings. The off-line phase is based on a genetic algorithm (GA) to generate high-quality mappings for a range of values for the dynamic parameters. A dynamic parameter space partitioning and sampling scheme is proposed that partitions the parameter space into a number of hyper-rectangles, within which the "best" mapping for each hyper-rectangle is stored in a mapping table. During the on-line phase, the actual dynamic parameters are observed and the off-line-derived mapping table is referenced to choose the most suitable mapping. Experimental results indicate that the semi-static approach outperforms a dynamic on-line approach and performs reasonably close to an infeasible on-line GA approach. Furthermore, the semi-static approach considerably outperforms the method of using the same mapping for all iterations. © 2005 Elsevier Inc. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdcen_HK
dc.relation.ispartofJournal of Parallel and Distributed Computingen_HK
dc.subjectAutomatic target recognitionen_HK
dc.subjectGenetic algorithmsen_HK
dc.subjectHeterogeneous computingen_HK
dc.subjectIterative task graphsen_HK
dc.subjectMappingen_HK
dc.subjectParallel processingen_HK
dc.subjectSchedulingen_HK
dc.titleA semi-static approach to mapping dynamic iterative tasks onto heterogeneous computing systemsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0743-7315&volume=66&issue=1&spage=77&epage=98&date=2006&atitle=A+Semi-Static+Approach+to+Mapping+Dynamic+Iterative+Tasks+onto+Heterogeneous+Computing+Systemsen_HK
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_HK
dc.identifier.authorityKwok, YK=rp00128en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.jpdc.2005.06.015en_HK
dc.identifier.scopuseid_2-s2.0-29244445082en_HK
dc.identifier.hkuros120623en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-29244445082&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume66en_HK
dc.identifier.issue1en_HK
dc.identifier.spage77en_HK
dc.identifier.epage98en_HK
dc.identifier.isiWOS:000234656800006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK
dc.identifier.scopusauthoridMacIejewski, AA=7103305993en_HK
dc.identifier.scopusauthoridSiegel, HJ=7101603637en_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK
dc.identifier.scopusauthoridGhafoor, A=7005954292en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats