A genetic algorithm for task scheduling on NoC using FDH cross efficiency.

*(English)*Zbl 1299.90388Summary: A CrosFDH-GA algorithm is proposed for the task scheduling problem on the NoC-based MPSoC regarding the multicriterion optimization. First of all, four common criterions, namely, makespan, data routing energy, average link load, and workload balance, are extracted from the task scheduling problem on NoC and are used to construct the DEA DMU model. Then the FDH analysis is applied to the problem, and a FDH cross efficiency formulation is derived for evaluating the relative advantage among schedule solutions. Finally, we introduce the DEA approach to the genetic algorithm and propose a CrosFDH-GA scheduling algorithm to find the most efficient schedule solution for a given scheduling problem. The simulation results show that our FDH cross efficiency formulation effectively evaluates the performance of schedule solutions. By conducting comparative simulations, our CrosFDH-GA proposal produces more metrics-balanced schedule solution than other multicriterion algorithms.

##### MSC:

90C59 | Approximation methods and heuristics in mathematical programming |

90B35 | Deterministic scheduling theory in operations research |

PDF
BibTeX
XML
Cite

\textit{S. Chai} et al., Math. Probl. Eng. 2013, Article ID 708495, 16 p. (2013; Zbl 1299.90388)

Full Text:
DOI

##### References:

[1] | A. S. Manne, “On the job-shop scheduling problem,” Operations Research, vol. 8, no. 2, pp. 219-223, 1960. · doi:10.1287/opre.8.2.219 |

[2] | M. H. Rothkopf, “Scheduling with random service times,” Management Science, vol. 12, no. 9, pp. 707-713, 1966. · Zbl 0199.23302 · doi:10.1287/mnsc.12.9.707 |

[3] | R. R. Muntz and E. G. Coffman Jr., “Preemptive scheduling of real-time tasks on multiprocessor systems,” Journal of the ACM, vol. 17, no. 2, pp. 324-338, 1970. · Zbl 0216.49702 · doi:10.1145/321574.321586 |

[4] | T. Malone, “Enterprise: a market-like task scheduler for distributed computing environments,” The Ecology of Computation, pp. 177-205, 1988. |

[5] | X. He, X. Sun, and G. Von Laszewski, “QoS guided Min-Min heuristic for grid task scheduling,” Journal of Computer Science and Technology, vol. 18, no. 4, pp. 442-451, 2003. · Zbl 1031.68034 · doi:10.1007/BF02948918 |

[6] | D. Geer, “Industry trends: chip makers turn to multicore processors,” Computer, vol. 38, no. 5, pp. 11-13, 2005. · Zbl 05088682 · doi:10.1109/MC.2005.160 |

[7] | W. J. Dally and B. Towles, “Route packets, not wires: on-chip interconnection networks,” in Proceedings of the 38th Design Automation Conference, pp. 684-689, June 2001. |

[8] | W. Vereecken, W. Van Heddeghem, D. Colle, M. Pickavet, and P. Demeester, “Overall ICT footprint and green communication technologies,” in Proceedings of the 4th International Symposium on Communications, Control, and Signal Processing (ISCCSP ’10), pp. 1-6, March 2010. · doi:10.1109/ISCCSP.2010.5463327 |

[9] | J. Huang, C. Buckl, A. Raabe, and A. Knoll, “Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems,” in Proceedings of the 19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing (PDP ’11), pp. 447-454, February 2011. · doi:10.1109/PDP.2011.10 |

[10] | B. Ge, N. Jing, W. He, and Z. Mao, “Contention and energy aware mapping for real-time applications on Network-on-Chip,” in Proceedings of the International Conference in SoC Design Conference (ISOCC ’12), pp. 72-76, 2012. |

[11] | A. Charnes, W. W. Cooper, and E. Rhodes, “Measuring the efficiency of decision making units,” European Journal of Operational Research, vol. 2, no. 6, pp. 429-444, 1978. · Zbl 0416.90080 · doi:10.1016/0377-2217(78)90138-8 |

[12] | A. Merkel, J. Stoess, and F. Bellosa, “Resource-conscious scheduling for energy efficiency on multicore processors,” in Proceedings of the 5th ACM EuroSys Conference on Computer Systems (EuroSys ’10), pp. 153-166, April 2010. · doi:10.1145/1755913.1755930 |

[13] | O. Sathappan, P. Chitra, P. Venkatesh, and M. Prabhu, “Modified genetic algorithm for multiobjective task scheduling on heterogeneous computing system,” International Journal of Information Technology, Communications and Convergence, vol. 1, no. 1, pp. 146-158, 2011. · doi:10.1504/IJITCC.2011.039282 |

[14] | J. M. N. Abad, S. K. Shekofteh, H. Tabatabaee, and M. Mehrnejad, “CoreIIScheduler: scheduling tasks in a multi-core-based grid using NSGA-II technique,” in Intelligent Informatics, pp. 507-518, Springer, New York, NY, USA, 2013. |

[15] | H. F. Sheikh and I. Ahmad, “Fast algorithms for thermal constrained performance optimization in DAG scheduling on multi-core processors,” in Proceedings of the International Green Computing Conference (IGCC ’11), pp. 1-6, July 2011. · doi:10.1109/IGCC.2011.6008554 |

[16] | A. J. Ruiz-Torres and F. J. López, “Using the FDH formulation of DEA to evaluate a multi-criteria problem in parallel machine scheduling,” Computers and Industrial Engineering, vol. 47, no. 2-3, pp. 107-121, 2004. · doi:10.1016/j.cie.2004.06.002 |

[17] | F. Samman, T. Hollstein, and M. Glesner, “New theory for deadlock-free multicast routing in wormhole-switched virtual-channelless networks-on-chip,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 4, pp. 544-557, 2011. · doi:10.1109/TPDS.2010.120 |

[18] | E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny, “QNoC: QoS architecture and design process for network on chip,” Journal of Systems Architecture, vol. 50, no. 2-3, pp. 105-128, 2004. · Zbl 05431999 · doi:10.1016/j.sysarc.2003.07.004 |

[19] | T. T. Ye, L. Benini, and G. De Micheli, “Analysis of power consumption on switch fabrics in network routers,” in Proceedings of the 39th Annual Design Automation Conference (DAC ’02), pp. 524-529, June 2002. |

[20] | E. Carvalho, N. Calazans, and F. Moraes, “Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs,” in Proceedings of the 18th IEEE/IFIP International Workshop on Rapid System Prototyping (RSP ’07), pp. 34-40, May 2007. · doi:10.1109/RSP.2007.26 |

[21] | M. Zakarya, N. Dilawar, M. A. Khattak, and H. Maqssod, “Energy efficient workload balancing algorithm for real-time tasks over multi-core,” World Applied Sciences Journal, vol. 22, no. 10, pp. 1431-1439, 2013. |

[22] | R. D. Banker, A. Charnes, and W. W. Cooper, “Some models for estimating technical and scale inefficiencies in data envelopment analysis,” Management Science, vol. 30, no. 9, pp. 1078-1092, 1984. · Zbl 0552.90055 · doi:10.1287/mnsc.30.9.1078 |

[23] | D. Deprins, L. Simar, and H. Tulkens, “Measuring labor-efficiency in post offices,” in Public Goods, Environmental Externalities and Fiscal Competition, pp. 285-309, Springer, New York, NY, USA, 2006. |

[24] | J. Doyle and R. Green, “Efficiency and cross-efficiency in DEA: derivations, meanings and uses,” Journal of the Operational Research Society, vol. 45, no. 5, pp. 567-578, 1994. · Zbl 0807.90016 · doi:10.1057/jors.1994.84 |

[25] | D. McFadden, “Cost, revenue, and profit functions,” in Histoy of Economic Thought Chapters, vol. 1, 1978. |

[26] | P. J. Agrell and J. Tind, “A dual approach to nonconvex frontier models,” Journal of Productivity Analysis, vol. 16, no. 2, pp. 129-147, 2001. · doi:10.1023/A:1011679226885 |

[27] | O. Sinnen, L. A. Sousa, and F. E. Sandnes, “Toward a realistic task scheduling model,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 3, pp. 263-275, 2006. · Zbl 05106808 · doi:10.1109/TPDS.2006.40 |

[28] | A. Makhorin, “GLPK (GNU linear programming kit),” 2006. |

[29] | H. O. Fried, C. A. K. Lovell, and S. S. Schmidt, The Measurement of Productive Efficiency and Productivity Growth, Oxford University Press, Oxford, UK, 2008. |

[30] | R. P. Dick, D. L. Rhodes, and W. Wolf, “TGFF: task graphs for free,” in Proceedings of the 1998 6th International Workshop on Hardware/Software Codesign, pp. 97-101, March 1998. · Zbl 05106631 · doi:10.1109/TPDS.2006.25 |

[31] | M.-Y. Wu and D. D. Gajski, “Hypertool: a programming aid for message-passing systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 1, no. 3, pp. 330-343, 1990. · Zbl 05106811 · doi:10.1109/71.80160 |

[32] | S. Kim and J. Browne, “A general approach to mapping of parallel computation upon multiprocessor architectures,” in Proceedings of the International Conference on Parallel Processing, 1988. |

[33] | R. T. Marler and J. S. Arora, “Survey of multi-objective optimization methods for engineering,” Structural and Multidisciplinary Optimization, vol. 26, no. 6, pp. 369-395, 2004. · Zbl 1243.90199 · doi:10.1007/s00158-003-0368-6 |

[34] | C. Song, W. Chang, L. Yubai, and Y. Zhongming, “A NoC simulation and verification platform based on systemC,” in Proceedings of the International Conference on Computer Science and Software Engineering (CSSE ’08), pp. 423-426, December 2008. · doi:10.1109/CSSE.2008.937 |

[35] | A. B. Kahng, L. Bin, L. Peh, and K. Samadi, “Orion 2.0: a fast and accurate NoC power and area model for early-stage design space exploration,” in Proceedings of the conference on Design, Automation and Test in Europe (DATE ’09), pp. 423-428, April 2009. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.