SIMPLE PERFORMANCE BOUNDS FOR MULTICORE AND PARALLEL CHANNEL SYSTEMS
Abstract
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. Ownes , 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 - IEEE Transactions on Aerospace and Electronic Systems 42(1), 327 (2006), DOI: 10.1109/TAES.2006.1603426. Crossref, ISI, Google Scholar
- Computer 33 (2008), DOI: 10.1109/MC.2008.209. ISI, Google Scholar
- Journal of Parallel and Distributed Computing 70, 183 (2010), DOI: 10.1016/j.jpdc.2009.05.002. Crossref, ISI, Google Scholar
-
V. Bharadwaj , Scheduling Divisible Loads in Parallel and Distributed Systems ( IEEE Computer Society Press , Los Alamitos, CA, USA , 1996 ) . Google Scholar - Cluster Computing 6, 7 (2003), DOI: 10.1023/A:1020958815308. Crossref, Google Scholar
- Computer 36, 63 (2003), DOI: 10.1109/MC.2003.1198238. Crossref, ISI, Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 22, 60 (1988). Google Scholar
- IEEE Transactions on Computers 37(12), 1627 (1988), DOI: 10.1109/12.9739. Crossref, ISI, Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 32, 34 (1996), DOI: 10.1109/7.481247. Crossref, ISI, Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 26, 511 (1990), DOI: 10.1109/7.106129. Crossref, ISI, Google Scholar
- IEEE Transaction on Systems, Man and Cybernetics 21, 1202 (1991), DOI: 10.1109/21.120070. Crossref, ISI, Google Scholar
- Parallel Computing 21, 1945 (1996), DOI: 10.1016/0167-8191(95)00046-1. Crossref, ISI, Google Scholar
- Foundations of Computing and Decision Sciences 21, 3 (1996). Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 29, 1216 (1993), DOI: 10.1109/7.259524. Crossref, ISI, Google Scholar
- IEEE Transactions on Aerospace and Electronic Systems 31, 555 (1995), DOI: 10.1109/7.381944. Crossref, ISI, Google 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 - IEEE Transactions on Systems, Man and Cybernetics 28, 245 (1998). Crossref, ISI, Google Scholar
- International Journal of Computers and Applications 26, 147 (2004), DOI: 10.2316/Journal.202.2004.3.202-1461. ISI, Google 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 - Discrete Applied Mathematics 76, 21 (1997), DOI: 10.1016/S0166-218X(96)00115-1. Crossref, ISI, Google 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 - 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 , Data intensive grid scheduling: multiple sources with capacity constraint , PDCS 2003: IASTED International Conference on Parallel and Distributed Computing and Systems ( 2003 ) . Google Scholar - Computers and Mathematics with Applications 1081 (2009), DOI: 10.1016/j.camwa.2009.07.046. Google Scholar
-
L. Marchal , 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 - IEEE Transactions on Parallel and Distributed Systems 21(4), 520 (2010). ISI, Google Scholar
-
M. Drozdowski , Scheduling for Parallel Processing ( Springer , New York, USA , 2009 ) . Crossref, Google Scholar -
H. Casanova , A. Legrand and Y. Robert , Parallel Algorithms ( CRC Press , Boca Raton, Florida, USA , 2009 ) . Google Scholar


