Maryam MURAD, Ishfaq HUSSAIN, Muhammad Yasir QADRI, Ayaz AHMAD, Nadia N. QADRI

Estimation of distribution-based multiobjective design space exploration for energy and throughput-optimized MPSoCs

Modern multicore architectures comprise a large set of components and parameters that require being matched to achieve the best balance between power consumption and throughput performance for a particular application domain. The exploration of design space for finding the best power–throughput trade-off is a combinatorial optimization problem with a large number of combinations, and. in general, its solution is prohibitively difficult to be explored exhaustively. However, fortunately, evolutionary algorithms EAs have the potential to efficiently solve this problem with reasonable computational complexity. In this paper, we consider a multiobjective design space exploration DSE problem with two conflicting objectives. The first objective corresponds to power consumption minimization while the second objective relates to throughput maximization. We approach this problem by employing the estimation of distribution algorithm EDA , which belongs to the family of EAs. The proposed EDA-based DSE EDA-DSE scheme efficiently selects the design parameters i.e. cache size, number of cores, and operating frequency with an efficient power–throughput ratio. The proposed scheme is verified using cycle-accurate simulations over a set of benchmarks and the simulation results show a significant reduction in energy-delay product for all benchmark applications when compared to the default baseline configuration and genetic algorithm.

Keywords:

Estimation of distribution algorithm, multiobjective optimization, design space exploration, energy/ throughput, multiprocessal system on chip,

PDF

___

[1] Palermo G, Silvano C, Zaccaria V. ReSPIR: A response surface-based Pareto iterative refinement for applicationspecific design space exploration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 2009; 28 (12): 1816-1829.
[2] Balasubramonian R, Albonesi D, Buyuktosunoglu A, Dwarkadas S. Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures. In: Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture; New York, NY, USA; 2000. pp. 245-257.
[3] Korthikanti VA, Agha G. Energy-performance trade-off analysis of parallel algorithms. In: USENIX Workshop on Hot Topics in Parallelism; Berkeley, CA; 2010. pp. 106-116.
[4] Mittal S, Cao Y, Zhang Z. Master: A multicore cache energy-saving technique using dynamic cache reconfiguration. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 2014; 22 (8): 1653-1665.
[5] Yang SH, Powell MD, Falsafi B, Vijaykumar T. Exploiting choice in resizable cache design to optimize deepsubmicron processor energy-delay. In: Proceedings of the Eighth International Symposium on High-Performance Computer Architecture; Boston, MA, USA; 2002. pp. 151-161.
[6] Monchiero M, Canal R, Gonzalez A. Design space exploration for multicore architectures: a power/performance/thermal view. In: Proceedings of the 20th Annual International Conference on Supercomputing; Queensland, Australia; 2006. pp. 177-186.
[7] Calborean H, Vinan L. Multi-objective optimization of advanced computer architectures using domain-knowledge. PhD, Lucian Blaga University of Sibiu, Sibiu, Romania, 2011.
[8] Calborean H, Jahr R, Ungerer T, Vintan L. Optimizing a superscalar system using multi-objective design space exploration. In: Proceedings of the 18th International Conference on Control Systems and Computer Science; Bucharest, Romania; 2011. pp. 339-346.
[9] Mariani G, Avasare P, Vanmeerbeeck G, Ykman-Couvreur C, Palermo G et al. An industrial design space exploration framework for supporting run-time resource management on multi-core systems. In: Design, Automation & Test in Europe Conference & Exhibition (DATE); Dresden, Germany; 2010. pp. 196-201.
[10] Qadri MY, McDonald Maier KD, Qadri NN. Energy and throughput aware fuzzy logic based reconfiguration for MPSoCs. Journal of Intelligent and Fuzzy Systems 2014; 26 (1): 101-113.
[11] Deb K. Multi-objective Optimization Using Evolutionary Algorithms. Vol. 16. Chichester, UK: John Wiley & Sons, 2001.
[12] Coello CAC, Van Veldhuizen DA, Lamont GB. Evolutionary Algorithms for Solving Multi-objective Problems. Vol. 242. New York, NY, USA: Springer, 2002.
[13] Yang XS. Metaheuristic optimization: algorithm analysis and open problems. arXiv preprint. arXiv: 12120220. 2012.
[14] Fonseca CM, Fleming PJ. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation 1995; 3 (1): 1-16.
[15] Larrañaga P, Lozano JA (editors). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Vol. 2. Boston, MA, USA: Springer, 2002, pp. 129-145.
[16] Li H, Zhang Q, Tsang E, Ford JA. Hybrid estimation of distribution algorithm for multiobjective knapsack problem. In: Evolutionary Computation in Combinatorial Optimization: 4th European Conference; Coimbra, Portugal; 2004. pp. 145-154.
[17] Aickelin U, Li J. An estimation of distribution algorithm for nurse scheduling. Annals of Operations Research 2007; 155 (1): 289-309.
[18] Patel A, Afram F, Ghose K. Marss-x86: A Qemu-based micro-architectural and systems simulator for x86 multicore processors. In: First International Qemu Users Forum; Grenoble, France; 2011. pp. 29-30.
[19] Yang P, Marchal P, Wong C, Himpe S, Catthoor F et al. Managing dynamic concurrent tasks in embedded real-time multimedia systems. In: Proceedings of the 15th International Symposium on System Synthesis; Kyoto, Japan; 2002. pp. 112-119.
[20] Wang W, Mishra P. Dynamic reconfiguration of two-level caches in soft real-time embedded systems. In: IEEE Computer Society Annual Symposium on VLSI; Florida, USA; 2009. pp. 145-150.
[21] Rawlins M, Gordon-Ross A. CPACT-The conditional parameter adjustment cache tuner for dual-core architectures. In: 2011 IEEE 29th International Conference on Computer Design; Amherst, MA, USA; 2011. pp. 396-403.
[22] Petrica P, Izraelevitz AM, Albonesi DH, Shoemaker CA. Flicker: a dynamically adaptive architecture for power limited multicore systems. ACM SIGARCH Computer Architecture News 2013; 41; 13-23.
[23] Reagen B, Shao YS, Wei GY, Brooks D. Quantifying acceleration: Power/performance trade-offs of application kernels in hardware. In: Proceedings of the International Symposium on Low Power Electronics and Design; Beijing, China; 2013. pp. 395-400.
[24] Dennis B, Muthukrishnan S. AGFS: Adaptive genetic fuzzy system for medical data classification. Applied Soft Computing 2014; 25: 242-252.
[25] Kerre EE, Nachtegael M. Fuzzy Techniques In Image Processing. Vol. 52. Heidelberg, Germany: Springer Science & Business Media, 2000.
[26] Silvano C, Fornaciari W, Palermo G, Zaccaria V, Castro F et al. MULTICUBE: Multi-objective design space exploration of multi-core architectures. In: VLSI 2010 Annual Symposium; Lixouri, Greece; 2010. pp. 47-63.
[27] Borges CC, Barbosa HJ. A non-generational genetic algorithm for multiobjective optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation; California, USA; 2000. pp. 172-179.
[28] Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 1994; 2 (3): 221-248.
[29] Ghezail F, Pierreval H, Hajri-Gabouj S. Multi objective optimization using ant colonies. In: Bertelle C, Duchamp CGHE, Kadri-Dahmani H (editors). Complex Systems and Self-organization Modelling. Berlin, Germany: Springer, 2009, pp. 65-70.
[30] Palesi M, Givargis T. Multi-objective design space exploration using genetic algorithms. In: Proceedings of the Tenth International Symposium on Hardware/Software Codesign, 2002; Colorado, USA; 2002. pp. 67-72.
[31] Wang G, Gong W, DeRenzi B, Kastner R. Design space exploration using time and resource duality with the ant colony optimization. In: Proceedings of the 43rd Annual Design Automation Conference; New York, NY, USA; 2006. pp. 451-454.
[32] Givargis T, Vahid F. Platune: A tuning framework for system-on-a-chip platforms. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems 2002; 21 (11): 1317-1327.
[33] Ferrandi F, Lanzi PL, Pilato C, Sciuto D, Tumeo A. Ant colony optimization for mapping, scheduling and placing in reconfigurable systems. In: 2013 NASA/ESA Conference on Adaptive Hardware and Systems; Torino, Italy; 2013. pp. 47-54.
[34] Li S, Ahn JH, Strong RD, Brockman JB, Tullsen DM et al. McPAT: An integrated power, area, and timing modeling framework for multicore and manycore architectures. In: Proceedings of International Symposium on Microarchitecture; New York, NY, USA; 2009. pp. 469-480.
[35] Kamble MB, Ghose K. Analytical energy dissipation models for low power caches. In: Proceedings International Symposium on Low Power Electronics and Design; Monterey, CA, USA; 1997. pp. 143-148.
[36] Qadri MY, McDonald-Maier KD. Analytical evaluation of energy and throughput for multilevel caches. In: 12th International Conference on Computer Modelling and Simulation; Cambridge, UK; 2010. pp. 598-603.
[37] Qadri MY, McDonald-Maier KD. Data cache-energy and throughput models: design exploration for embedded processors. EURASIP Journal on Embedded Systems 2009; 2009: 725438.
[38] Chen T, Lehre PK, Tang K, Yao X. When is an estimation of distribution algorithm better than an evolutionary algorithm? In: 2009 IEEE Congress on Evolutionary Computation; Trondheim, Norway; 2009. pp. 1470-1477.
[39] Dikmen O, Akın HL, Alpaydın E. Estimating distributions in genetic algorithms. In: International Symposium on Computer and Information Sciences; Antalya, Turkey; 2003. pp. 521-528.
[40] Očenášek J, Schwarz J. The parallel Bayesian optimization algorithm. In: The State of the Art in Computational Intelligence, Proceedings of the European Symposium on Computational Intelligence; Košice, Slovakia; 2000. pp. 61-67.
[41] Costa M, Minisci E. MOPED: a multi-objective Parzen-based estimation of distribution algorithm for continuous problems. In: International Conference on Evolutionary Multi-Criterion Optimization; Faro, Portugal; 2003. pp. 282-294.
[42] Barros M, Barros MF, Guilherme J, Horta N. Analog Circuits and Systems Optimization Based on Evolutionary Computation Techniques. Erfurt, Germany: Springer, 2010.
[43] Mühlenbein H, Bendisch J, Voigt HM. From recombination of genes to the estimation of distributions II. Continuous parameters. In: Parallel Problem Solving from Nature; Berlin, Germany; 1996. pp. 188-197.
[44] Blake G, Dreslinski RG, Mudge T. A survey of multicore processors. IEEE Signal Processing Magazine 2009; 26 (6): 26-37.
[45] Hill MD, Marty MR. Amdahl’s law in the multicore era. Computer 2008; 41 (7): 33-38.
[46] Wu Y, Wang Y, Liu X. Multi-population based univariate marginal distribution algorithm for dynamic optimization problems. Journal of Intelligent & Robotic Systems 2010; 59 (2): 127-144.
[47] Pelikan M. Hierarchical Bayesian optimization Algorithm. Berlin, Heidelberg: Springer, 2005.
[48] Mühlenbein H, Mahnig T. FDA-A scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation 1999; 7 (4): 353-376.
[49] Pelikan M, Sastry K, Goldberg DE. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning 2002; 31 (3): 221-258.
[50] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 2002; 6 (2): 182-197.
[51] Shim VA, Tan KC, Cheong CY. A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews) 2012; 42 (5): 682-691.
[52] Muralimanohar N, Balasubramonian R, Jouppi NP. CACTI 6.0: A tool to model large caches. HP Laboratories 2009; 1: 1-24
[53] Woo SC, Ohara M, Torrie E, Singh JP, Gupta A. The SPLASH-2 programs: characterization and methodological considerations. SIGARCH Computer Architecture News 1995; 23: 24-36.
[54] Bailey DH. FFTs in external of hierarchical memory. In: Proceedings of the 1989 ACM/IEEE Conference on Supercomputing; New York, NY, USA; 1989. pp. 234-242.
[55] Subtil RF, Carrano EG, Souza MJ, Takahashi RH. Using an enhanced integer NSGA-II for solving the multiobjective generalized assignment problem. In: IEEE Congress on Evolutionary Computation; Barcelona, Spain; 2010. pp. 1-7.
[56] Eeckhout L, Nussbaum S, Smith JE, De Bosschere K. Statistical simulation: adding efficiency to the computer designer’s toolbox. IEEE Micro 2003; 23 (5): 26-38.
[57] Fernandes CM, Merelo J, Ramos V, Rosa AC. A self-organized criticality mutation operator for dynamic optimization problems. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation; New York, NY, USA; 2008. pp. 937-944.

Turkish Journal of Electrical Engineering and Computer Science-Cover

ISSN: 1300-0632
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv