World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SIMPLE PERFORMANCE BOUNDS FOR MULTICORE AND PARALLEL CHANNEL SYSTEMS

    A simple modification of existing divisible load scheduling algorithms, boosting link speed by M for M parallel channels per link, allows time optimal load scheduling and performance prediction for parallel channel systems. The situation for multicore models is more complex but can be handled by a substitution involving equivalent processor speed. These modifications yield upper bounds on such parallel systems' performance. This concept is illustrated for ideal single level (star) tree networks under a variety of scheduling policies. Less than ideal parallelism can also be modeled though mechanisms of inefficiency require further research.

    References

    • J. D. Owneset al., Research Challenges for ON-CHIP Interconnections Networks (IEEE Computer Society, 2007) pp. 272–1732. Google Scholar
    • T. G.   Robertazzi , Networks and Grids: Technology and Theory ( Springer , NY, USA , 2007 ) . Google Scholar
    • M. Moges and T. G. Robertazzi, IEEE Transactions on Aerospace and Electronic Systems 42(1), 327 (2006), DOI: 10.1109/TAES.2006.1603426. Crossref, ISIGoogle Scholar
    • M. D. Hill and M. R. Marty, Computer 33 (2008), DOI: 10.1109/MC.2008.209. ISIGoogle Scholar
    • X.-H. Sun and Y. Chen, Journal of Parallel and Distributed Computing 70, 183 (2010), DOI: 10.1016/j.jpdc.2009.05.002. Crossref, ISIGoogle Scholar
    • V.   Bharadwaj et al. , Scheduling Divisible Loads in Parallel and Distributed Systems ( IEEE Computer Society Press , Los Alamitos, CA, USA , 1996 ) . Google Scholar
    • V. Bharadwaj, D. Ghose and T. G. Robertazzi, Cluster Computing 6, 7 (2003), DOI: 10.1023/A:1020958815308. CrossrefGoogle Scholar
    • T. G. Robertazzi, Computer 36, 63 (2003), DOI: 10.1109/MC.2003.1198238. Crossref, ISIGoogle Scholar
    • Y. C. Cheng and T. G. Robertazzi, IEEE Transactions on Aerospace and Electronic Systems 22, 60 (1988). Google Scholar
    • R. Agrawal and H. V. Jgadish, IEEE Transactions on Computers 37(12), 1627 (1988), DOI: 10.1109/12.9739. Crossref, ISIGoogle Scholar
    • J. Sohn and T. G. Robertazzi, IEEE Transactions on Aerospace and Electronic Systems 32, 34 (1996), DOI: 10.1109/7.481247. Crossref, ISIGoogle Scholar
    • Y. C. Cheng and T. G. Robertazzi, IEEE Transactions on Aerospace and Electronic Systems 26, 511 (1990), DOI: 10.1109/7.106129. Crossref, ISIGoogle Scholar
    • S. Bataineh and T. G. Robertazzi, IEEE Transaction on Systems, Man and Cybernetics 21, 1202 (1991), DOI: 10.1109/21.120070. Crossref, ISIGoogle Scholar
    • J. Blazewicz and M. Drozdowski, Parallel Computing 21, 1945 (1996), DOI: 10.1016/0167-8191(95)00046-1. Crossref, ISIGoogle Scholar
    • J. Blazewicz and M. Drozdowski, Foundations of Computing and Decision Sciences 21, 3 (1996). Google Scholar
    • T. G. Robertazzi, IEEE Transactions on Aerospace and Electronic Systems 29, 1216 (1993), DOI: 10.1109/7.259524. Crossref, ISIGoogle Scholar
    • V. Bharadwaj, D. Ghose and V. Mani, IEEE Transactions on Aerospace and Electronic Systems 31, 555 (1995), DOI: 10.1109/7.381944. Crossref, ISIGoogle Scholar
    • Y.   Yang and H.   Casanova , UMR: A multi-round algorithm for scheduling divisible workloads , IPDPS'03: Proceedings of the International Parallel and Distributed Processing Symposium ( 2003 ) . Google Scholar
    • D. Piriyakumar and C. Murthy, IEEE Transactions on Systems, Man and Cybernetics 28, 245 (1998). Crossref, ISIGoogle Scholar
    • J. Hung and T. Robertazzi, International Journal of Computers and Applications 26, 147 (2004), DOI: 10.2316/Journal.202.2004.3.202-1461. ISIGoogle Scholar
    • O.   Beaumont , A.   Legrand and Y.   Robert , Optimal algorithms for scheduling divisible workloads on heterogeneous systems , HCW'2003: 12th Heterogeneous Computing Workshop ( 2003 ) . Google Scholar
    • J. Blazewicz and M. Drozdowski, Discrete Applied Mathematics 76, 21 (1997), DOI: 10.1016/S0166-218X(96)00115-1. Crossref, ISIGoogle Scholar
    • A. L. Rosenberg, Sharing partitionable workloads in heterogeneous NOWs: greedier is not better, Proceedings of the IEEE International Conference on Cluster Computing (2001) pp. 124–131. Google Scholar
    • P. F.   Dutot , Divisible load on heterogeneous linear array , IPDPS'03: Proceedings of the International Parallel and Distributed Processing Symposium ( 2003 ) . Google Scholar
    • M.   Moges and T.   Robertazzi , Optimal divisible load scheduling and markov chain models , Proceedings of the 2003 Conference on Information Sciences and Systems ( 2003 ) . Google Scholar
    • T. G. Robertazzi, Parallel Processing Letters  (2011). Google Scholar
    • K.   Ko and T.   Robertazzi , Scheduling in an environment of multiple job submissions , Proceedings of the 2002 Conference on Information Sciences and Systems ( 2002 ) . Google Scholar
    • H.   Wong et al. , Data intensive grid scheduling: multiple sources with capacity constraint , PDCS 2003: IASTED International Conference on Parallel and Distributed Computing and Systems ( 2003 ) . Google Scholar
    • M. A. Moges, D. Yu and T. G. Robertazzi, Computers and Mathematics with Applications 1081 (2009), DOI: 10.1016/j.camwa.2009.07.046. Google Scholar
    • L.   Marchal et al. , A realistic network/application model for scheduling loads on large-scale platforms , Proceedings of the International Parallel and Distributed Processing Symposium ( 2005 ) . Google Scholar
    • T.   Lammie and T.   Robertazzi , A linear daisy chain with two divisible load sources , Proceedings of 2005 Conference on Information Sciences and Systems ( 2005 ) . Google Scholar
    • D.   Yu and T.   Robertazzi , Multi-source grid scheduling for divisible loads , Proceedings of 2006 Conference on Information Sciences and Systems ( 2006 ) . Google Scholar
    • J. Jingxi, B. Veeravalli and J. Weissman, IEEE Transactions on Parallel and Distributed Systems 21(4), 520 (2010). ISIGoogle Scholar
    • M.   Drozdowski , Scheduling for Parallel Processing ( Springer , New York, USA , 2009 ) . CrossrefGoogle Scholar
    • H.   Casanova , A.   Legrand and Y.   Robert , Parallel Algorithms ( CRC Press , Boca Raton, Florida, USA , 2009 ) . Google Scholar