Open Access Open Access  Restricted Access Subscription or Fee Access

Particle Swarm Thread Scheduling for Parallelizable Dependent Tasks in Heterogeneous Grid Environment

Y. Maheshwaran, P. Mathiyalagan, Dr. S. N. Sivanandam

Abstract


Scheduling workloads is a difficult task. In order to design efficient scheduling algorithms for dependent workloads, it is required to have a good in-depth knowledge of basic scheduling strategies and graph theory. This paper analyzes the distribution of sequential dependent tasks and the scheduling behavior in heterogeneous computational grid environments. In this paper, we also propose a new thread based algorithm for scheduling dependent tasks and optimize the algorithm using heuristic principles. Introducing Particle swarm based Thread parallel Scheduling; we have successfully demonstrated a new heuristic algorithm for scheduling of dependent tasks. Experiments prove the increased performance and efficiency after incorporation of the optimization techniques.

Keywords


Grid Computing, Dependent Tasks, Thread Algorithm, Particle Swarm Optimization.

Full Text:

PDF

References


H.S. Stone, “Critical load factors in two-processor distributed systems”, IEEE Transactions on Software Engineering, SE-4 (1978).

Z. Michalewicz, B.B. Fogel, “How to Solve It: Modern Heuristics”, Springer-Verlag, 2002.

A. Ernst, H. Hiang and M. Krishnamoorthy, “Mathematical programming approaches for solving task allocation problems”, Proc. of the 16th National Conf. of Australian Society of Operations Research, 2001.

A. Billionnet, M.C. Costa and A. Sutter, “An efficient algorithm for a task allocation problem”, Journal of ACM 39 (1992).

J. Kennedy and R.C. Eberhart, “Particle swarm optimization”, Proceedings IEEE Int’l. Conf. on Neural Networks, vol. IV, 1995.

R.C. Eberhart and Y. Shi, “Evolving artificial neural networks”, Proceedings Int’l. Conf. on Neural Networks and Brain, 1998.

V. Tandon, “Closing the gap between CAD/CAM and optimized CNC end milling”, Master thesis, Purdue School of Engineering and Technology, Indiana University Purdue University Indianapolis, 2000.

H. Yoshida, K. Kawata, Y. Fukuyama and Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage stability, Proceedings Int’l. Conf. on Intelligent System Application to Power Systems, 1999.

N. Shigenori, G. Takamu, Y. Toshiku and F. Yoshikazu, A hybrid particle swarm optimization for distribution state estimation, IEEE Transactions on Power Systems 18 (2003).

K.E. Parsopoulos and M.N. Vrahatis, Recent approaches to global optimization problems through particle swarm optimization, Natural Computing 1 (2002).

M. Clerc and. Kennedy, The particle swarm explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation 6(2002).

I.C. Trelea, “The particle swarm optimization algorithm: convergence analysis and parameter selection”, Information Processing Letters 85 (2003).

J.M. Schopf, “A General Architecture for Scheduling on the Grid”, special issue of JPDC on Grid Computing, 2002.

T. Hacker and W. Thigpen, “Distributed Accounting on the Grid,” Grid Forum Working Draft, 2007.

G. Manimaran and C.S.R. Murthy, “An Efficient Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 3, Mar. 1998. (IPDPS ’00), 2000.

D. Abramson, I. Foster, J. Giddy, A. Lewis, R. Sosic, R.R. Sutherst and M. Hawa, “Stochastic Evaluation of Fair Scheduling with Applications to Quality-of-Service in Broadband Wireless Access Networks,” PhD dissertation, Univ. of Kansas, Aug. 2003.

A. Demers, S. Keshav, and S. Shenker, “Design and Analysis of a Fair Queuing Algorithm,” Proc. ACM SIGCOMM ’89, Sept. 1989.

D. Bertsekas and R. Gallager, “Data Networks”, second ed., Prentice Hall, 1992

K. Ramamritham, J.A. Stankovic, and P.-F. Shiah, “Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 2, Apr. 1990

G. Manimaran, C.S.R. Murthy, M. Vijay, and K. Ramamritham, “New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems,” J. Parallel and Distributed Computing, vol. 44, no. 2, Aug. 1997

F. Kelly, “Charging and Rate Control for Elastic Traffic,” European Trans. Telecomm., vol. 8, no. 1, 1997.

Z. Cao and E.W. Zegura, “Utility Max-Min: An Application- Oriented Bandwidth Allocation Scheme,” Proc. IEEE INFOCOM ’99, vol. 2, Mar. 1999.

M.L. Dertouzos and A.K.-L. Mok, “Multi processor On-Line Scheduling for Hard Real Time Tasks,” IEEE Trans. Software Eng., Dec. 1989. Bertsekas and R. Gallager, Data Networks, second ed. Prentice Hall, 1992.

B. Vandalore, S. Fahmy, R. Jain, R. Goyal, and M. Goyal, “General Weighted Fairness and Its Support in Explicit Rate Switch Algorithms,” Computer Comm., vol. 23, no. 2, Jan. 2000.

D. Liu, N. Ansari, and E. Hou, “Fairness Criterion for Allocating Resources in Input Queued Switches,” IEE Electronic Letters, vol. 37, no. 19, Sept. 2001.[13] I. Foster and C. Kesselman, “Globus: A Metacomputing Infrastructure Toolkit,” Int’l J. Supercomputer Applications, vol. 11, no. 2, 1997.

S. Keshav, “An Engineering Approach to Computer Networking”, Addison-Wesley, 1997.

D.S. Johnson, “Fast Algorithms for Bin Packing,” Computer and System Sciences, vol. 8, 1974.

R. Wolski, J.S. Plank, J. Brevik, and T. Bryan, “G-commerce: Market Formulations Controlling Resource Allocation on the Computational Grid,” Proc. Int’l Parallel and Distributed Processing Symp. (IPDPS ’01), Apr. 2001.

Nikolaos D. Doulamis, Anastasios D. Doulamis, Emmanouel A. Varvarigos, and Theodora A. Varvarigou, “Fair Scheduling Algorithms in Grids” IEEE Trans on Parallel and Distributed Systems, vol. 18, no. 11, November 2007.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.