International Research journal of Management Science and Technology

  ISSN 2250 - 1959 (online) ISSN 2348 - 9367 (Print) New DOI : 10.32804/IRJMST

Impact Factor* - 6.2311


**Need Help in Content editing, Data Analysis.

Research Gateway

Adv For Editing Content

   No of Download : 79    Submit Your Rating     Cite This   Download        Certificate

A NOT ON DAG FOR TASK SCHEDULING TECHNIQUES

    1 Author(s):  JUGMENDRA SINGH

Vol -  7, Issue- 3 ,         Page(s) : 43 - 54  (2016 ) DOI : https://doi.org/10.32804/IRJMST

Abstract

In order to support the ability to push and pull changesets between multiple instances of the same repository, we need a specially designed structure for representing multiple versions of things. The structure we use is called a Directed Acyclic Graph (DAG), a design which is more expressive than a purely linear model. The history of everything in the repository is modeled as a DAG. DAG has been extensively used in multiprocessor systems workflow modeling. In other words, if a computational problem can be divided into a number of subtasks, the data dependencies between these subtasks are usually described by means of a directed acyclic graph (DAG) also called task graph. In general, synthetic DAGs are used for evaluation and classification of existing scheduling heuristics, proposal for scheduling approach and comparison with existing heuristics. As a result, we can identify the need to provide the appropriate tool that will allow researchers to evaluate their scheduling algorithms under similar conditions, by generating various types of DAGs based on both realistic parallel algorithms patterns.

  1. U. Banerjee, "Loop transformations for restructuring compilers: the foundations”, Springer, pp. 19, 1993.
  2. Bang-Jensen and Jørgen "acyclic digraphs, digraphs: theory, algorithms and applications”, Springer-Verlag, pp. 32–34, 2008,
  3. Bang-Jensen, J. Gutin, Z. Gregory, "Transitive digraphs, transitive closures and reductions, digraphs: theory, algorithms and applications”, Springer, pp. 36–39, ISBN 2008.
  4. A. E. Bender and Williamson and S. Gill "Linear extensions -topological sorts", A short course in discrete mathematics, Courier dover publications, pp. 142, 2005.
  5. Christofides and Nicos, “Graph theory: an algorithmic approach”, Academic press, pp. 170-174. 1975.
  6. H.T. Cormen, E.C. Leiserson  and L.R. Rivest, “Introduction to Algorithms” (2nd ed.). MIT Press and MCgraw-hill, pp. 549–552. 2001
  7. Cormen  ,”Single-source shortest paths in directed acyclic graphs”, Section 24.2, pp. 592-595, 2001,
  8. Cormen et , “Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595-601”. 2001
  9. Cormen et al. 2001, p. 966.
  10. W.G. Furnas and J. Zacks, "Multitrees: enriching and reusing hierarchical structure", Proc. SIGCHI conference on human factors in computing systems,  pp. 330-336, 1994.
  11. R.M. Garey and S.D. Johnson, “computers and intractability: a guide to the theory of np-completeness”, Problems GT7 and GT8, pp. 191-192, 1979.
  12. Gross, L. Jonathan, J. Yellen and P. Zhang, “Handbook of Graph Theory” 2nd ed., CRC Press, pp. 1181, 2013
  13. F. Harary and Z.R. Norman, “Structural models: an introduction to the theory of directed graphs”, John Wiley & Sons, p. 63, 1965.
  14. Hartigan, A.John, and A. Manchek Wong. "Algorithm AS 136: A k-means clustering algorithm." Applied statistics pp.100-108, 1979.
  15. D. Jungnickel, “Graphs, networks and algorithms, algorithms and computation in mathematics”, Springer, pp. 92-93, 2012.
  16. Kozen and Dexter, “The design and analysis of algorithms, monographs in computer science”, Springer, pp. 9, 1992.
  17. I. Mitrani, “Simulation techniques for discrete event systems”, Cambridge university press, pp. 27, 1982.
  18. Mtibaa, Abdellatif, Bouraoui Ouni, and Mohamed Abid. "An efficient list scheduling algorithm for time placement problem." Computers & electrical engineering 33, no. 4, pp. 285-298, 2007.
  19. A H. Al-Mutawa, J. Dietrich, S. Marsland, and C McCartin, "On the shape of circular dependencies in Java programs", 23rd Australian software engineering conference, IEEE, pp. 48-57,. 2014.
  20. Park, Chan-Ik, and Tae-Young Choe. "An optimal scheduling algorithm based on task duplication." In parallel and distributed systems, 2001. icpads 2001. proceedings. eighth international conference on, IEEE, pp. 9-14, 2001.
  21. J. Picard,"Maximal closure of a graph and applications to combinatorial problems", Management Science 22 (11): PP. 1268-1272, 1976.
  22. W. L. Price, "Global optimization by controlled random search." Journal of Optimization Theory and Applications 40, no. 3 pp. 333-348. 1983.
  23. G. Rebane,  and J. Pearl "The recovery of causal poly-trees from statistical data", in Proc. 3rd annual conference on uncertainty in artificial intelligence,  pp. 222-228, 1987.

  25. H. El-Rewini and T.G. Lewis, “Scheduling parallel program tasks onto arbitrary target machines”, J. Parallel and distributed computing, vol. 9, no. 2, pp. 138-153, 1990.
  26. Robinson, Jacob, and Yahya Rahmat-Samii. "Particle swarm optimization in electromagnetics." Antennas and Propagation, IEEE Transactions on 52, no. 2 pp. 397-407, 2004.
  27. Rolland, Erik, David A. Schilling, and John R. Current. "An efficient tabu search procedure for the p-median problem." European journal of operational research 96, no. 2 pp. 329-342. 1997.
  28. R. Romero,  R. A. Gallego, and A. Monticelli. "Transmission system expansion planning by simulated annealing." Power Systems, IEEE Transactions on 11, no. 1 pp. 364-369, 1996.
  29. R. Sedgewick, and K.Wayne, "Unique topological ordering algorithms”, 4th ed. Addison-Wesley, pp. 598-599, 2011.
  30. Sim, Kwang Mong and Weng Hong Sun. "Ant colony optimization for routing and load-balancing: survey and new directions." Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on 33, no. 5  pp. 560-572, 2003.
  31. Sivanandam, S. N., and S. N. Deepa. Introduction to genetic algorithms. Springer Science & Business Media, 2007.
  32. Skiena and S. Steven ,” For depth-first search based topological sorting algorithm”, Springer, pp. 179-181, 2009.
  33. Y. N. Srikant, and P. Shankar, “the compiler design handbook: optimizations and machine code generation”, (2nd ed.), CRC Press, pp. 19–39, 2007.
  34. Stanley and P. Richard , "Acyclic orientations of graphs", Discrete mathematics 5 (2):, doi:10.1016/0012-365X(73)90108-8, pp.171–178,1973
  35. K.Thulasiraman and Swamy, “acyclic directed graphs: graph theory and algorithms”, John Wiley and Son, pp. 118, 1992.
  36. H. Topcuoglu, S. Hariri, and M. Wu, “performance-effective and low-complexity task scheduling for heterogeneous computing”, IEEE trans. parallel and distributed systems, vol. 13, no. 3, pp. 260-274,  2002.
  37. H. Topcuoglu, S. Hariri, and M. Wu, “Task scheduling algorithms for heterogeneous processors”, Proc. eighth heterogeneous computing workshop (HCW), pp. 3-14, 1999.
  38. J. X.Wang, “What every engineer should know about decision making under uncertainty”, CRC Press, pp. 160. 2002.

*Contents are provided by Authors of articles. Please contact us if you having any query.






Bank Details