Estimation of distribution-based multiobjective design space exploration for energy and throughput-optimized MPSoCs
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 matchedto 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 problemwith 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 reasonablecomputational complexity. In this paper, we consider a multiobjective design space exploration (DSE) problem with twoconflicting objectives. The first objective corresponds to power consumption minimization while the second objectiverelates 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 thedesign 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 showa significant reduction in energy-delay product for all benchmark applications when compared to the default baselineconfiguration and genetic algorithm.
___
- [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.