Application of an Adaptive Genetic Algorithm for Task Mapping Optimisation on a Wormhole-based Real-time Network-on-Chip
Resumo
The task mapping problem of real-time applications onto a homogeneous multiple processors system-on-a-chip (MPSoC) is an NP-hard problem that can be addressed using search-based heuristic methods. A particular case is the priority preemptive wormhole-based Network-on-a-Chip (NoC) communication architecture that takes into consideration the end-to-end schedulability analysis. In this paper, we present a parameter Adaptive Genetic Algorithm (AGA) capable of efficiently achieving schedulable task placements. In our experiments, we perform analytic methods in different scenarios with multiple synthetically generated real-time applications, as well as various platforms with a ranging number of processors to provide a statistical study comparing our algorithm against a standard genetic algorithm approach.
Palavras-chave:
Multiprocessor/Multicore/Manycore Systems, Performance Evaluation and Optimization
Referências
W. Wolf A. Jerraya G. Martin "Multiprocessor System-on-Chip (MPSoC) Technology" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. 27 pp. 1701-1713 oct 2008.
G. De Micheli L. Benini "Networks on chips: 15 years later" Computer no. 5 pp. 10-11 2017.
S. Hesham J. Rettkowski D. Goehringer M. A. Abd El Ghany "Survey on Real-Time Networks-on-Chip" IEEE Transactions on Parallel and Distributed Systems vol. 28 pp. 1500-1517 may 2017.
E. Bolotin I. Cidon R. Ginosar 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.
A. Mello L. Tedesco N. Calazans F. Moraes "Virtual channels in networks on chip" pp. 178 2005.
W. J. Dally "Virtual-Channel Flow Control" IEEE Transactions on Parallel and Distributed Systems vol. 3 no. 2 pp. 194-205 1992.
M. R. Garey D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness New York:W. H. Freeman vol. 29 2002.
P. Mesidis L. S. Indrusiak "Genetic mapping of hard real-time applications onto NoC-based MPSoCs - A first approach" 6th International Workshop on Reconfigurable Communication-Centric Systems-on-Chip ReCoSoC 2011 - Proceedings 2011.
A. Racu L. S. Indrusiak "Using genetic algorithms to map hard real-time on NoC-based systems" 7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC) pp. 1-8 jul 2012.
L. S. Indrusiak "End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration" Journal of Systems Architecture vol. 60 no. 7 pp. 553-561 2014.
N. Audsley A. Burns M. Richardson K. Tindell A. Wellings "Applying new scheduling theory to static priority pre-emptive scheduling" Software Engineering Journal vol. 8 no. 5 pp. 284 1993.
Z. Shi A. Burns "Real-Time Communication Analysis for On- Chip Networks with Wormhole Switching" ACM/IEEE International Symposium on Networks-on-Chip pp. 161-170 2008.
L. C. Liu J. W. Layland "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment" tech. rep. 1973.
G. Karafotias M. Hoogendoorn Á. E. Eiben "Parameter control in evolutionary algorithms: Trends and challenges" IEEE Transactions on Evolutionary Computation vol. 19 no. 2 pp. 167-187 2014.
J. Derrac S. García D. Molina F. Herrera "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms" Swarm and Evolutionary Computation vol. 1 no. 1 pp. 3-18 2011.
I. Triguero S. González J. M. Moyano S. García López J. Alcal á Fernández J. Luengo Martín A. Fernández Hilario J. Díaz L. Sánchez F. Herrera et al. "Keel 3.0: an open source software for multi-stage analysis in data mining" 2017.
L. S. Indrusiak A. Burns B. Nikolić "Buffer-aware bounds to multi-point progressive blocking in priority-preemptive nocs" 2018 Design Automation & Test in Europe Conference & Exhibition (DATE) pp. 219-224 2018.
G. De Micheli L. Benini "Networks on chips: 15 years later" Computer no. 5 pp. 10-11 2017.
S. Hesham J. Rettkowski D. Goehringer M. A. Abd El Ghany "Survey on Real-Time Networks-on-Chip" IEEE Transactions on Parallel and Distributed Systems vol. 28 pp. 1500-1517 may 2017.
E. Bolotin I. Cidon R. Ginosar 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.
A. Mello L. Tedesco N. Calazans F. Moraes "Virtual channels in networks on chip" pp. 178 2005.
W. J. Dally "Virtual-Channel Flow Control" IEEE Transactions on Parallel and Distributed Systems vol. 3 no. 2 pp. 194-205 1992.
M. R. Garey D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness New York:W. H. Freeman vol. 29 2002.
P. Mesidis L. S. Indrusiak "Genetic mapping of hard real-time applications onto NoC-based MPSoCs - A first approach" 6th International Workshop on Reconfigurable Communication-Centric Systems-on-Chip ReCoSoC 2011 - Proceedings 2011.
A. Racu L. S. Indrusiak "Using genetic algorithms to map hard real-time on NoC-based systems" 7th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC) pp. 1-8 jul 2012.
L. S. Indrusiak "End-to-end schedulability tests for multiprocessor embedded systems based on networks-on-chip with priority-preemptive arbitration" Journal of Systems Architecture vol. 60 no. 7 pp. 553-561 2014.
N. Audsley A. Burns M. Richardson K. Tindell A. Wellings "Applying new scheduling theory to static priority pre-emptive scheduling" Software Engineering Journal vol. 8 no. 5 pp. 284 1993.
Z. Shi A. Burns "Real-Time Communication Analysis for On- Chip Networks with Wormhole Switching" ACM/IEEE International Symposium on Networks-on-Chip pp. 161-170 2008.
L. C. Liu J. W. Layland "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment" tech. rep. 1973.
G. Karafotias M. Hoogendoorn Á. E. Eiben "Parameter control in evolutionary algorithms: Trends and challenges" IEEE Transactions on Evolutionary Computation vol. 19 no. 2 pp. 167-187 2014.
J. Derrac S. García D. Molina F. Herrera "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms" Swarm and Evolutionary Computation vol. 1 no. 1 pp. 3-18 2011.
I. Triguero S. González J. M. Moyano S. García López J. Alcal á Fernández J. Luengo Martín A. Fernández Hilario J. Díaz L. Sánchez F. Herrera et al. "Keel 3.0: an open source software for multi-stage analysis in data mining" 2017.
L. S. Indrusiak A. Burns B. Nikolić "Buffer-aware bounds to multi-point progressive blocking in priority-preemptive nocs" 2018 Design Automation & Test in Europe Conference & Exhibition (DATE) pp. 219-224 2018.
Publicado
19/11/2019
Como Citar
DE BARROS, Jesse; AYALA-RINCÓN, Mauricio; QUINTERO, Carlos.
Application of an Adaptive Genetic Algorithm for Task Mapping Optimisation on a Wormhole-based Real-time Network-on-Chip. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 9. , 2019, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 17-24.
ISSN 2237-5430.
