علوم رایانش و فناوری اطلاعات

نگاشت و زمان‌بندی همزمان وظایف و ارتباطات انرژی‌آگاه بی‌درنگ در ساختارهای چندهسته‌ای

نویسندگان

دانشکده فنی و مهندسی، دانشگاه شاهد، ﺗﻬﺮان، اﻳﺮان

چکیده

در این مقاله یک متدلوژی نگاشت و زمان‌بندی بی‌درنگ انرژی‌آگاه برای برنامه‌ریزی همزمان وظایف و ارتباطات با هدف حل سریع با جواب نزدیک بهینه درتراشه‌های چند هسته‌ای ارایه می‌شود. متدلوژی پیشنهادی با برخورداری از ساختار نوین کروموزوم در الگوریتم ژنتیک و برخورداری از تابع جهش شبیه‌سازی گداخت، دارای قابلیت جلوگیری از تولید راه‌حل‌های غیرممکن جهت کاهش زمان تولید جواب نزدیک بهینه است. تحلیل ما از نتایج آزمایشات در فضای نانو تکنولوژی نشان می‌دهد که در نگاشت و زمان‌بندی همزمان نسبت به روش سنتی ژنتیک از سرعت همگرایی بسیار خوبی برخورداری است و به‌طور متوسط در ساختار زمان‌بندی حدود 10% و در ساختار نگاشت بیش از 90% بهبود سرعت در زمان اجرا، همراه با تولید جواب نزدیک بهینه را نشان می‌دهد.

کلیدواژه‌ها

  • [1] A. Kumar, M. Shafique, A. Kumar, and J. Henke,
  • "Mapping on Multi/Many-core Systems: Survey of Currentand Emerging Trends,"Proc. DAC, pp. 338-342, 2013.
  • [2] S. Borkar, "Designing Reliable Systems from UnreliableComponents: The Challenges ofTransistor Variability andDegradation,"IEEE Micro, vol. 25, pp. 10-16, 2005.
  • [3] O. Eduard, and et. al., "Energy Efficiency and RenewableEnergy Iintegration in Data Centres," Strategies andmodelling review, Renewable and Sustainable EnergyReviews, no.42, pp. 429-445, 2015.
  • [4] S. Mittal, "A Survey of Techniques for Improving EnergyEfficiency in Embedded Computing Systems,"InternationalJournal of Computing Aided Engineering and Technology,vol. 6, no. 4, pp. 450-459, 2014.
  • [5] P. Nathaniel, D. Blaauw, and D. Sylvester, "Low-PowerNear-Threshold Design: Techniques to Improve EnergyEfficiency Energy-EfficientNear-Threshold Design HasBeen Proposed to Increase Energy Efficiency Across a Wid,"IEEE Solid-State Circuits Magazine, vol. 7, no.2, pp. 49-57,2015.
  • [6] J. Sartori, A. Pant, R. Kumar, and P. Gupta, "Variation-aware Speed Binning ofMulti-core Processors,"11thACM/IEEE International Symposium on Quality ElectronicDesign, ISQED, San Jose, 2010.
  • [7] R. Viswanath, V. Wakharkar, A. Watew, and V.Lbonheur, "Thermal Performance Challenges from Silicon toSystems,"Intel Technology Journal, vol.4, no.3, pp. 1-16,2000.[Online].Available:http://www.intel.com/technology/itj/ q32000/articles/art_4.htm.
  • [8] L. Y. Lin, and et. al., "Communication-driven TaskBinding for Multiprocessor with Latency InsensitiveNetwork-on-chip,"ASP-DAC, pp. 39–44, 2005.
  • [9] G. Ascia, V. Catania, and M. Palesi, "Multi-objectiveMapping for Mesh-based NoCArchitectures,"CODES+ISSS,pp. 182–187, 2004.
  • [10] International technology roadmap for semiconductors,2010, http://www.itrs.net/Links/2010ITRS/Home2010.htm.
  • [11] A. Mahabadi, SM. Zahedi, and A. Khonsari, "ReliableEnergy-aware Application Mapping and Voltage–frequencyIslandPartitioning for GALS-based NoC,"Journal ofComputer and System Sciences, vol. 79, no.4, pp.57–74,2013.
  • [12] B. Khodabandeloo, A. Khonsari, F. Gholamian, M. H.Hajiesmaili, A. Mahabadi, andH. Noori, "Scenario-basedQuasi-static Task Mapping and Scheduling for Temperature-efficient MPSoCDesign under Process Variation," Microprocessors and Microsystems, vol. 38, pp. 399–414,2014.
  • [13] J. Castrillon, A. Tretter,R. Leupers, and G. Ascheid, "Communication-aware Mapping of KPN Applications ontoHeterogeneous MPSoCs,"DAC, pp. 1266–1271, 2012.
  • [14] W. Che, and K. S. Chatha, "Unrolling and Retiming ofStream Applications onto Embedded Multicore Processors," DAC, pp. 1272–1277, 2012.
  • [15] S. Gupta, G. Agarwal, and V. Kumar, "Task Schedulingin Multiprocessor System Using Genetic Algorithm," Machine Learning and Computing (ICMLC), SecondInternational Conference, pp. 267-271, 2010.
  • [16] S. Sivanandam, and P. Visalakshi, "Dynamic TaskScheduling with Load Balancing using Parallel OrthogonalParticle Swarm Optimisation,"International Journal ofBio-Inspired Computation, vol. 1, pp. 276-286, 2009.
  • [17] S. Ninomiya, K. Sakanushi, Y. Takeuchi, and M. Imai, "Task Allocation and Scheduling for Voltage-FrequencyIslands Applied NoC-based MPSoC Considering NetworkCongestion,"Embedded Multicore Socs (MCSoC), IEEE 6thInternational Symposium, pp. 107-112, 2012.
  • [18] G. Chen, F. Li, S. andSon, M. Kandemir, "ApplicationMapping for Chip Multiprocessors,"DAC, pp. 620–625,2008.
  • [19] S. Banerjee, and N. Dutt, "Efficient Search SpaceExploration for HW-SW Partitioning,"InternationalConference on Hardware/Software Codesign and SystemSynthesis, pp. 122-127, 2004.
  • [20] A. Hartman, D. Thomas, and B. Meyer, "A Case forLifetime-aware Task Mapping in Embedded ChipMultiprocessors,"CODES+ISSS, pp. 145 –154, 2010.
  • [21] E. Seo, Y. Koo, andJ. Lee, "Dynamic Repartitioningof Real-time Schedule on a Multicore Processor for EnergyEfficiency,"Proc. Int. Conf. Embedded and UbiquitousComputing, pp. 69–78, Aug. 2006.
  • [22] J. Hu, and R. Marculescu, "Energy- and performance-aware mapping for regular NoC architectures,"IEEE Trans.Comp.-Aided Des. Integ. Cir. Sys., no. 4, pp. 551–562, 2005.
  • [23] C. Marcon, A. Borin, A. Susin, L. Carro, and F.Wagner, "Time and energy efficient mapping of embeddedapplications onto NoCs,"ASP-DAC, pp. 33–38, 2005.
  • [24] C. Marcon, E. Moreno, N. Calazans, and F. Moraes, "Comparison of network-on-chip mapping algorithmstargeting low energy consumption. Computers DigitalTechniques,"IET, pp. 471–482, 2008.
  • [25] B. H. Meyer, A. S. Hartman, and D. E. Thomas, "Cost-effective Slack Allocation for Lifetime Improvement in NoC-based MPSoCs,"DATE, pp. 1596–1601, 2010.
  • [26] H. Orsila, and et. al., "Automated Memory-awareApplication Distribution for Multi-processor System-on-Chips,"J. Syst. Archit., no. 11, pp.795–815, 2007.
  • [27] X. Wu, and et. al., "Genetic Algorithms for IntegratingCell Formation with Machine Layout and Scheduling," Computers & Industrial Engineering, vol. 5, no. 2, pp.277-289, 2007.
  • [28] J. Choi, H. Oh, S. Kim, and S. Ha, "ExecutingSynchronous Dataflow Graphs on a SPM-based MulticoreArchitecture,"DAC, pp. 664–671, 2012.
  • [29] S. Manolache, P. Eles, and Z. Peng, "Task Mapping andPriority Assignment for Soft Real-time Applications underDeadline Miss Ratio Constraints,"ACM Trans. Embed.Comput. Syst.,vol. 19, pp.13–19, 2008.
  • [30] H. Javaid, and S. Parameswaran, "A Design Flow forApplication Specific Heterogeneous PipelinedMultiprocessor Systems,"DAC, pp. 250–253, 2009.
  • [31] M. Ruggiero, and et. al., "Communication-awareAllocation and Scheduling Framework for Stream-orientedMulti-processor Systems-on-chip,"DATE, pp. 3–8, 2006.
  • [32] L. Thiele, I. Bacivarov, W. Haid, and K. Huang, "Mapping Applications to Tiled Multiprocessor EmbeddedSystems,"ACSD, pp. 29–40, 2007.
  • [33] S. Murali, M. Coenen, A. Radulescu, K. Goossens, andG. De Micheli, "A methodology for Mapping Multiple Use-cases onto Networks on Chips,"DATE, pp. 118–123, 2006.
  • [34] C.-E. Rhee, H.-Y. Jeong, and S. Ha, "Many-to-ManyCore-Switch Mapping in 2-D Mesh NoC Architectures," ICCD, pp. 438–443, 2004.
  • [35] C. M. Chen, and C. T. King, "Using Integer LinearProgramming for Instruction Scheduling and RegisterAllocation in Multi-issue Processors,"Multi-IssueProcessors. Computers and Mathematics with Applications,1997.
  • [36] Y. Zhang, D. Parikh, K.Sankaranarayanan, K. Skadron,and M. Stan, "HotLeakage: Atemperature-aware Model ofSub Threshold and Gate Leakage for Architects,"Tech. Rep.CS-2003-05, University of Virginia, 2003.
  • [37] K. Bowman, S. Duvall, and J. Meindl, "Impact of Die-to-die and within Die Parameter Fluctuations on theMaximum Clock Frequency Distribution for Giga ScaleIntegration,"IEEE J. Solid State Circuits, vol. 37, no. 2, pp.183-190, 2002.
  • [38] W. Zhang, G. Sun, and S. Bin, "A Novel TaskCommunication and Scheduling Algorithm for NoC-basedMPSoC,"International Journal of Smart Home, vol. 9, no.10, pp. 179-188, 2015.
  • [39] R. Dick. "Embedded Systems Synthesis BenchmarksSuite (e3s)," http://www.ece.northwestern.edu/ dickrp/e3s/.
  • [40] E. L. Lawler, and C.U. Martel, "SchedulingPeriodically Occurring Tasks on Multiple Processors,"Information Processing Ltrs., vol. 7, no. 1, pp. 9-12,1981.
  • [41] T. Chantem, X.S. Hu, and R.P. Dick, "Temperature-aware Scheduling and Assignment for Hard Real-timeApplications on MPSoCs,"IEEE Trans. VLSI System, pp.1884-1897, 2011.
  • [42] G. Link, and N. Vijaykrishnan, "Thermal Trends inEmerging Technologies," In Proc. Int. Symp. Quality ofElectronic Design, pp. 625–632, 2006.
  • [43] W. Huang, K. Rajamani, M. R. Stan, and K. Skadron, "Scaling with Design Constraints Predicting the Future ofBig Chips,"IEEE Micro special issue on Big Chips, 2011.
  • [44] M. Momtazpour, E. Sanaei, and M.Goudarzi, "Power-yield Optimization in MPSoCTask Scheduling under Process Variation," ISQED, pp. 747-754, 2010.
  • [45] CPLEX 11.1ILOG: http://www.ilog.com/product/cplex/, 2013.
  • [46] HotSpot: http://lava.cs.virginia.edu/HotSpot/, 2013.
  • [47] R. Teodorescu, B. Greskamp, J. Nakano, S. Sarangi, A.Tiwari, and J. Torrellas, "VARIUS: A Model of ParameterVariation and Resulting Timing Errors for Microarchitects,"2nd Workshopon Architectural Support for GigascaleIntegration, San Diego, USA, 2007.
  • [48] S. R. Sarangi, B. Greskamp, R. Teodorescu, J. Nakano,A. Tiwari, and J. Torrellas, "VARIUS: A Model of ProcessVariation and Resulting Timing Errors for Microarchitects," IEEE Trans. on Semiconductor Manufacturing, vol. 21, no.1, 2008.
  • [49] A. Bonfietti, L. Benini, M. Lombardi, and M. Milano, "An Efficient and Complete Approach for Throughput-maximal SDFAllocation and Scheduling on Multi-corePlatforms,"DATE, pp. 897–902, 2010.
  • [50] N. Satish, K. Ravindran, and K. Keutzer, "ADecomposition-based Constraint Optimization ApproachforStatically Scheduling Task Graphs with CommunicationDelaysto Multiprocessors,"DATE, pp. 57–62, 2007.
  • [51] L. Thiele, L. Schor, H. Yang, and I. Bacivarov, "Thermal-awareSystem Analysis and Software Synthesis forEmbedded Multi-processors,"DAC, pp. 268–273, 2011.
  • [52] D. Wu, B. M. Al-Hashimi, and P. Eles,"Scheduling andMapping of Conditional Task Graphs for the Synthesis ofLowPower Embedded Systems,"DATE, pp. 10090, 2003.
  • [53] Y. Markovskiy, E. Caspi, R. Huang, J. Yeh, M. Chu, J.Wawrzynek, and A. DeHon, Analysis of Quasi-StaticScheduling Techniques in a Virtualized ReconfigurableMachine. Proceedings of ACM/SIGDA Tenth InternationalSymposium on Field-Programmable Gate Arrays, pp.196-205, 2002.
علوم رایانش و فناوری اطلاعات
دوره 13، شماره 2
پاییز و زمستان
آذر 1394