{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:59:55Z","timestamp":1760241595066,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T00:00:00Z","timestamp":1526947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We address image processing workflow scheduling problems on a multicore digital signal processor cluster. We present an experimental study of scheduling strategies that include task labeling, prioritization, resource selection, and digital signal processor scheduling. We apply these strategies in the context of executing the Ligo and Montage applications. To provide effective guidance in choosing a good strategy, we present a joint analysis of three conflicting goals based on performance degradation. A case study is given, and experimental results demonstrate that a pessimistic scheduling approach provides the best optimization criteria trade-offs. The Pessimistic Heterogeneous Earliest Finish Time scheduling algorithm performs well in different scenarios with a variety of workloads and cluster configurations.<\/jats:p>","DOI":"10.3390\/a11050076","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T03:14:24Z","timestamp":1527045264000},"page":"76","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["PHEFT: Pessimistic Image Processing Workflow Scheduling for DSP Clusters"],"prefix":"10.3390","volume":"11","author":[{"given":"Alexander Yu.","family":"Drozdov","sequence":"first","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow 141701, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5029-5212","authenticated-orcid":false,"given":"Andrei","family":"Tchernykh","sequence":"additional","affiliation":[{"name":"Computer Science Department, CICESE Research Center, 22860 Ensenada, Baja California, Mexico"},{"name":"School of Electrical Engineering and Computer Science, South Ural State University, Chelyabinsk 454080, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey V.","family":"Novikov","sequence":"additional","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow 141701, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor E.","family":"Vladislavlev","sequence":"additional","affiliation":[{"name":"Moscow Institute of Physics and Technology, Moscow 141701, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raul","family":"Rivera-Rodriguez","sequence":"additional","affiliation":[{"name":"Computer Science Department, CICESE Research Center, 22860 Ensenada, Baja California, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,22]]},"reference":[{"key":"ref_1","unstructured":"Conway, R.W., Maxwell, W.L., and Miller, L.W. (1967). Theory of Scheduling, Addison-Wesley."},{"key":"ref_2","unstructured":"B\u0142a\u017cewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., and Weglarz, J. (2007). Handbook on Scheduling: From Theory to Applications, Springer."},{"key":"ref_3","first-page":"98","article-title":"32-bit superscalar DSP-processor with floating point arithmetic","volume":"7","author":"Myakochkin","year":"2013","journal-title":"Compon. Technol."},{"key":"ref_4","unstructured":"(2018, May 15). TigerSHARC Embedded Processor ADSP-TS201S. Available online: http:\/\/www.analog.com\/en\/products\/processors-dsp\/dsp\/tigersharc-processors\/adsp-ts201s.html#product-overview."},{"key":"ref_5","unstructured":"Muchnick, S.S. (1997). Advanced Compiler Design and Implementation, Morgan Kauffman."},{"key":"ref_6","unstructured":"Novikov, S.V. (2005). Global Scheduling Methods for Architectures with Explicit Instruction Level Parallelism. [Ph.D. Thesis, Institute of Microprocessor Computer Systems RAS (NIISI)]."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/1084805.1084816","article-title":"Scheduling of scientific workflows in the askalon grid environment","volume":"34","author":"Wieczorek","year":"2005","journal-title":"ACM Sigmod Rec."},{"key":"ref_8","unstructured":"Bittencourt, L.F., and Madeira, E.R.M. (December, January 27). A dynamic approach for scheduling dependent tasks on the xavantes grid middleware. Proceedings of the 4th International Workshop on Middleware for Grid Computing, Melbourne, Australia."},{"key":"ref_9","first-page":"217","article-title":"Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms","volume":"14","author":"Jia","year":"2006","journal-title":"Sci. Program."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Ramakrishnan, A., Singh, G., Zhao, H., Deelman, E., Sakellariou, R., Vahi, K., Blackburn, K., Meyers, D., and Samidi, M. (2007, January 14\u201317). Scheduling data-intensive workflows onto storage-constrained distributed resources. Proceedings of the 7th IEEE Symposium on Cluster Computing and the Grid, Rio De Janeiro, Brazil.","DOI":"10.1109\/CCGRID.2007.101"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Szepieniec, T., and Bubak, M. (October, January 29). Investigation of the dag eligible jobs maximization algorithm in a grid. Proceedings of the 2008 9th IEEE\/ACM International Conference on Grid Computing, Tsukuba, Japan.","DOI":"10.1109\/GRID.2008.4662819"},{"key":"ref_12","unstructured":"Singh, G., Su, M.-H., Vahi, K., Deelman, E., Berriman, B., Good, J., Katz, D.S., and Mehta, G. (February, January 29). Workflow task clustering for best effort systems with Pegasus. Proceedings of the 15th ACM Mardi Gras conference, Baton Rouge, LA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s10723-005-9011-7","article-title":"Optimizing grid-based workflow execution","volume":"3","author":"Singh","year":"2005","journal-title":"J. Grid Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10723-015-9340-0","article-title":"Online Bi-Objective Scheduling for IaaS Clouds with Ensuring Quality of Service","volume":"14","author":"Tchernykh","year":"2016","journal-title":"J. Grid Comput."},{"key":"ref_15","first-page":"2277","article-title":"Worst Case Behavior of List Algorithms for Dynamic Scheduling of Non-Unit Execution Time Tasks with Arbitrary Precedence Constrains. IEICE-Tran Fund Elec","volume":"8","author":"Tchernykh","year":"2008","journal-title":"Commun. Comput. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0377-2217(02)00236-9","article-title":"Algorithms for Dynamic Scheduling of Unit Execution Time Tasks","volume":"146","author":"Rodriguez","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/j.dam.2008.03.005","article-title":"Idle Regulation in Non-Clairvoyant Scheduling of Parallel Jobs","volume":"157","author":"Tchernykh","year":"2009","journal-title":"Disc. Appl. Math."},{"key":"ref_18","first-page":"219","article-title":"Pegasus: A framework for mapping complex scientific workflows onto distributed systems","volume":"13","author":"Deelman","year":"2005","journal-title":"Sci. Program."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Blythe, J., Jain, S., Deelman, E., Vahi, K., Gil, Y., Mandal, A., and Kennedy, K. (2005, January 9\u201312). Task Scheduling Strategies for Workflow-based Applications in Grids. Proceedings of the IEEE International Symposium on Cluster Computing and the Grid, Cardiff, Wales, UK.","DOI":"10.1109\/CCGRID.2005.1558639"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10723-015-9337-8","article-title":"CA-DAG: Modeling Communication-Aware Applications for Scheduling in Cloud Computing","volume":"14","author":"Kliazovich","year":"2016","journal-title":"J. Grid Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s10723-009-9144-1","article-title":"Towards the scheduling of multiple workflows on computational grids","volume":"8","author":"Bittencourt","year":"2010","journal-title":"J. Grid Comput."},{"key":"ref_22","unstructured":"Zhao, H., and Sakellariou, R. (2006, January 25\u201329). Scheduling multiple dags onto heterogeneous systems. Proceedings of the 20th International Parallel and Distributed Processing Symposium, Rhodes Island, Greece."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/71.993206","article-title":"Performance-effective and low-complexity task scheduling for heterogeneous computing","volume":"13","author":"Topcuouglu","year":"2002","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_24","unstructured":"Sakellariou, R., and Zhao, H. (2004, January 26). A hybrid heuristic for dag scheduling on heterogeneous systems. Proceedings of the 13th IEEE Heterogeneous Computing Workshop, Santa Fe, NM, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Bittencourt, L.F., Sakellariou, R., and Madeira, E.R. (2010, January 17\u201319). DAG Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm. Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, Pisa, Italy.","DOI":"10.1109\/PDP.2010.56"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhao, H., and Sakellariou, R. (2003). An Experimental Investigation into the Rank Function of the Heterogeneous Earliest Finish Time Scheduling Algorithm, Springer.","DOI":"10.1007\/978-3-540-45209-6_28"},{"key":"ref_27","unstructured":"(2018, May 15). Pegasus. Available online: http:\/\/pegasus.isi.edu\/workflow_gallery\/index.php."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Hirales-Carbajal, A., Tchernykh, A., Roblitz, T., and Yahyapour, R. (2010, January 19\u201323). A grid simulation framework to study advance scheduling strategies for complex workflow applications. Proceedings of the 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), Atlanta, GA, USA.","DOI":"10.1109\/IPDPSW.2010.5470918"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s10723-012-9215-6","article-title":"Multiple Workflow Scheduling Strategies with User Run Time Estimates on a Grid","volume":"10","author":"Tchernykh","year":"2012","journal-title":"J. Grid Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/s10723-017-9410-6","article-title":"Adaptive Resource Allocation in Computational Grids with Runtime Uncertainty","volume":"15","author":"Tchernykh","year":"2017","journal-title":"J. Grid Comput."},{"key":"ref_31","unstructured":"Tchernykh, A., Schwiegelsohn, U., Talbi, E.-G., and Babenko, M. (2016). Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability. J. Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1772","DOI":"10.1016\/j.procs.2015.05.387","article-title":"Towards Understanding Uncertainty in Cloud Computing Resource Provisioning","volume":"51","author":"Tchernykh","year":"2015","journal-title":"Proced. Comput. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1137\/040608015","article-title":"Optimality measures for performance profiles","volume":"16","author":"Dolan","year":"2006","journal-title":"Siam. J. Optim."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/76\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:05:20Z","timestamp":1760195120000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,22]]},"references-count":33,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["a11050076"],"URL":"https:\/\/doi.org\/10.3390\/a11050076","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,5,22]]}}}