The sorted nodes in leveled DAG division algorithm and critical path on processor

https://doi.org/10.21744/irjmis.v6n1.769

Authors

  • Mark Damon Gorn Harvard University, Cambridge, Massachusetts, United States
  • Matt Orchid Jack Harvard University, Cambridge, Massachusetts, United States
  • Conan Ballmon Enderson Harvard University, Cambridge, Massachusetts, United States

Keywords:

critical path, division algorithm, leveled DAG, processor, sorted nodes

Abstract

Scheduling Algorithms, mostly List based static algorithms are considered for HDCS. Based on the algorithms, SNLDD, HEFT, CPOP, and implementation of SNLDD with Superior Performance Optimization Procedure are studied. In this paper, the outcome performance of the developed SNLDD algorithm is correlated with current existing algorithms mainly for HeDCSs. The comparative study between the proposed SNLDD algorithm with modified optimization procedure SPOP and HEFT with CPOP are evaluated based on the schedule length, speedup, efficiency of running programs and quality parameters with respect to memory in parallel computer systems has achieved a high speed up and fast execution time by SNLDD.

Downloads

Download data is not yet available.

References

Arabnejad, V., Bubendorfer, K., & Ng, B. (2017). Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources. Future Generation Computer Systems, 75, 348-364. https://doi.org/10.1016/j.future.2017.01.002

Bahnasawy, N. A., Omara, F., Koutb, M. A., & Mosa, M. (2011). Optimization procedure for algorithms of task scheduling in high performance heterogeneous distributed computing systems. Egyptian Informatics Journal, 12(3), 219-229. https://doi.org/10.1016/j.eij.2011.10.001

Hao, Q., Shen, W., Xue, Y., & Wang, S. (2010). Task network-based project dynamic scheduling and schedule coordination. Advanced Engineering Informatics, 24(4), 417-427. https://doi.org/10.1016/j.aei.2010.07.001

Kessler, C. W. (1998). Scheduling expression DAGs for minimal register need. Computer Languages, 24(1), 33-53. https://doi.org/10.1016/S0096-0551(98)00002-2

Lam, K. Y., Zhu, C. J., Chang, Y. H., Hsieh, J. W., Huang, P. C., Poon, C. K., & Wang, J. (2014). Garbage collection of multi-version indexed data on flash memory. Journal of Systems Architecture, 60(8), 630-643. https://doi.org/10.1016/j.sysarc.2014.06.004

Lin, L., & Gen, M. (2018). Hybrid evolutionary optimisation with learning for production scheduling: state-of-the-art survey on algorithms and applications. International Journal of Production Research, 56(1-2), 193-223. https://doi.org/10.1080/00207543.2018.1437288

Serna, M. (2008). Parallel Algorithms for Two Processors Precedence Constraint Scheduling: 2003; Jung, Serna, Spirakis. Encyclopedia of Algorithms, 627-629. https://doi.org/10.1007/978-0-387-30162-4

Shi, Z., Jeannot, E., & Dongarra, J. J. (2006, September). Robust task scheduling in non-deterministic heterogeneous computing systems. In 2006 IEEE International Conference on Cluster Computing (pp. 1-10). IEEE. https://doi.org/10.1109/CLUSTR.2006.311868

Venkateswaran, R., & Mazumder, P. (1994). A survey of DA techniques for PLD and FPGA based systems. Integration, the VLSI journal, 17(3), 191-240. https://doi.org/10.1016/0167-9260(94)90001-9

Wang, L., Khan, S. U., Chen, D., KołOdziej, J., Ranjan, R., Xu, C. Z., & Zomaya, A. (2013). Energy-aware parallel task scheduling in a cluster. Future Generation Computer Systems, 29(7), 1661-1670. https://doi.org/10.1016/j.future.2013.02.010

Yuan, Y., Li, X., Wang, Q., & Zhu, X. (2009). Deadline division-based heuristic for cost optimization in workflow scheduling. Information Sciences, 179(15), 2562-2575. https://doi.org/10.1016/j.ins.2009.01.035

Zhu, C. J., Lam, K. Y., Chang, Y. H., & Ng, J. K. Y. (2015). Linked Block-based Multiversion B-Tree index for PCM-based embedded databases. Journal of Systems Architecture, 61(9), 383-397. https://doi.org/10.1016/j.sysarc.2015.08.002

Published

2019-01-31

How to Cite

Gorn, M. D., Jack, M. O., & Enderson, C. B. (2019). The sorted nodes in leveled DAG division algorithm and critical path on processor. International Research Journal of Management, IT and Social Sciences, 6(1), 113–121. https://doi.org/10.21744/irjmis.v6n1.769

Issue

Vol. 6 No. 1 (2019): January

Section

Peer Review Articles
Copyright & Licensing

Articles published in the International Research Journal of Management, IT and Social sciences (IRJMIS) are available under Creative Commons Attribution Non-Commercial No Derivatives Licence (CC BY-NC-ND 4.0). Authors retain copyright in their work and grant IRJMIS right of first publication under CC BY-NC-ND 4.0. Users have the right to read, download, copy, distribute, print, search, or link to the full texts of articles in this journal, and to use them for any other lawful purpose.

Articles published in IRJMIS can be copied, communicated and shared in their published form for non-commercial purposes provided full attribution is given to the author and the journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.

This copyright notice applies to articles published in IRJMIS volumes 7 onwards. Please read about the copyright notices for previous volumes under Journal History.