Publicado

2014-05-01

Static and dynamic task mapping onto network on chip multiprocessors

Mapeo estático y dinámico de tareas en sistemas multiprocesador, basados en redes en circuito integrado

DOI:

https://doi.org/10.15446/dyna.v81n185.34867

Palabras clave:

Task mapping, Multiprocessor System-on-Chip (MPSoC), Networks on Chip (NoC), Population-based Incremental Learning (PBIL) (en)
Mapeo de tareas, Sistemas integrados multiprocesador (MPSoC), Redes en circuito integrado (NoC), Aprendizaje incremental basado en población (PBIL) (es)

Descargas

Autores/as

  • Freddy Bolaños-Martínez Universidad Nacional de Colombia
  • José Edison Aedo Universidad de Antioquia
  • Fredy Rivera-Vélez Universidad de Antioquia
Due to its scalability and flexibility, Network-on-Chip (NoC) is a growing and promising communication paradigm for Multiprocessor System-on-Chip (MPSoC) design. As the manufacturing process scales down to the deep submicron domain and the complexity of the system increases, fault-tolerant design strategies are gaining increased relevance. This paper exhibits the use of a Population-Based Incremental Learning (PBIL) algorithm aimed at finding the best mapping solutions at design time, as well as to finding the optimal remapping solution, in presence of single-node failures on the NoC. The optimization objectives in both cases are the application completion time and the network's peak bandwidth. A deterministic XY routing algorithm was used in order to simulate the traffic conditions in the network which has a 2D mesh topology. Obtained results are promising. The proposed algorithm exhibits a better performance, when compared with other reported approaches, as the problem size increases.
Las redes en circuito integrado (NoC) representan un importante paradigma de uso creciente para los sistemas multiprocesador en circuito integrado (MPSoC), debido a su flexibilidad y escalabilidad. Las estrategias de tolerancia a fallos han venido adquiriendo importancia, a medida que los procesos de manufactura incursionan en dimensiones por debajo del micrómetro y la complejidad de los diseños aumenta. Este artículo describe un algoritmo de aprendizaje incremental basado en población (PBIL), orientado a optimizar el proceso de mapeo en tiempo de diseño, así como a encontrar soluciones de mapeo óptimas en tiempo de ejecución, para hacer frente a fallos de único nodo en la red. En ambos casos, los objetivos de optimización corresponden al tiempo de ejecución de las aplicaciones y al ancho de banda pico que aparece en la red. Las simulaciones se basaron en un algoritmo de ruteo XY determinístico, operando sobre una topología de malla 2D para la NoC. Los resultados obtenidos son prometedores. El algoritmo propuesto exhibe un desempeño superior a otras técnicas reportadas cuando el tamaño del problema aumenta.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Marculescu R., Ogras U. Y., Peh L. S., Jerger N. E., Hoskote Y. Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives. Trans. Comp.-Aided Des. Integ. Cir. Sys., vol. 28, no. 1, pp. 3–21, Jan. 2009.

Huang J., Buckl C., Raabe A., Knoll A. Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems. In Parallel, Distributed and Network-Based Processing (PDP), 2011 19th Euromicro International Conference on, pp. 447 –454, Feb. 2011.

Rajaei R., Hessabi S., Vahdat B. V. An energy-aware methodology for mapping and scheduling of concurrent applications in MPSOC architectures. In Electrical Engineering (ICEE), 2011 19th Iranian Conference on, pp. 1 –6, May 2011.

Ghosh P., Sen A., Hall A. Energy efficient application mapping to noc processing elements operating at multiple voltage levels. In Networks-on-Chip, 2009. NoCS 2009. 3rd ACM/IEEE International Symposium on, pp. 80 –85, May 2009.

Mandelli M., Ost L., Carara E., Guindani G. , Gouvea T., Medeiros G., Moraes F. Energy-aware dynamic task mapping for NoC-based MPSoCs. In Circuits and Systems (ISCAS), 2011 IEEE International Symposium on, pp. 1676 –1679, May 2011.

Marculescu R. Networks-on-chip: The quest for on-chip fault-tolerant communication. In VLSI, 2003 Proceedings of the IEEE Computer Society Annual Symposium on, pp. 8 – 12, Feb. 2003.

Schranzhofer A., Chen J. J., Santinelli L., Thiele L. Dynamic and adaptive allocation of applications on mpsoc platforms. In Design Automation Conference (ASP-DAC), 2010 15th Asia and South Pacific, pp. 885 –890, Jan. 2010.

Wildermann S., Ziermann T., Teich J. Run time mapping of adaptive applications onto homogeneous noc-based reconfigurable architectures. In Field-Programmable Technology 2009. FPT 2009. International Conference on, pp. 514 –517, Dec. 2009.

Carvalho E. de S., Calazans N., Moraes F. Dynamic task mapping for MPSoCs. Design Test of Computers, IEEE, vol. 27, no. 5, pp. 26 –35, Oct. 2010.

Singh A. K., Srikanthan T., Kumar A., Jigang W. Communication aware heuristics for run-time task mapping on NoC-based MPSoC platforms. J. Syst. Archit., vol. 56, no. 7, pp. 242–255, Jul. 2010.

Carvalho E., Calazans N., Moraes F. Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs. In Proceedings of the 18th IEEE/IFIP International Workshop on Rapid System Prototyping, ser. RSP '07. Washington, DC, USA: IEEE Computer Society, pp. 34–40, 2007.

Derin O., Kabakci D., Fiorin L. Online task remapping strategies for fault-tolerant network-on-chip multiprocessors. In Networks on Chip (NoCS), 2011 Fifth IEEE/ACM International Symposium on, pp. 129 –136, May 2011.

Tafesse B., Raina A., Suseela J. , Muthukumar V. Efficient scheduling algorithms for MPSoC systems. In Information Technology: New Generations (ITNG), 2011 Eighth International Conference on, pp. 683 –688, April 2011.

Russell S. J., Norvig P. Artificial Intelligence: A Modern Approach. 2nd ed. Pearson Education, 2003.

Jang W., Pan D. Z. A3Map: Architecture-aware analytic mapping for Networks-on-Chip. ACM Trans. Des. Autom. Electron. Syst., vol. 17, pp. 26:1–26:22, July 2012.

Singh A. K., Kumar A., Srikanthan T. A hybrid strategy for mapping multiple throughput-constrained applications on MPSoCs. In Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems, CASES '11, (New York, NY, USA), pp. 175–184, ACM, 2011.

Antunes E., Soares M., Aguiar A., Filho S. J., Sartori M., Hessel F., Marcon C. A. M. Partitioning and dynamic mapping evaluation for energy consumption minimization on noc-based MPSoC. In ISQED (K. A. Bowman, K. V. Gadepally, P. Chatterjee, M. M. Budnik, and L. Immaneni, eds.), pp. 451–457, IEEE, 2012.

Antunes E., Aguiar A., Johann F. S., Sartori M. , Hessel F., Marcon C. Partitioning and mapping on NoC-based MPSoC: an energy consumption saving approach. In Proceedings of the 4th International Workshop on Network on Chip Architectures, NoCArc '11, (New York, NY, USA), pp. 51–56, ACM, 2011.

He O., Dong S., Jang W., Bian J., Pan D. Z. UNISM: Unified scheduling and mapping for general Networks on Chip. IEEE Trans. VLSI Syst., vol. 20, no. 8, pp. 1496–1509, 2012.

Hosseinabady M., Nunez-Yanez J. L. Run-time stochastic task mapping on a large scale Network-on-Chip with dynamically reconfigurable tiles. IET Computers and Digital Techniques, vol. 6, no. 1, pp. 1–11, 2012.

Hamedani P. K., Hessabi S., Sarbazi-Azad H., Jerger N. D. E. Exploration of temperature constraints for thermal aware mapping of 3D Networks on Chip. In PDP (R. Stotzka, M. Schiffers, and Y. Cotronis, eds.), pp. 499–506, IEEE, 2012.

Wang C., Yu L., Liu L., Chen T. Packet triggered prediction based task migration for Network-on-Chip. In Proceedings of the 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing, PDP '12, (Washington, DC, USA), pp. 491–498, IEEE Computer Society, 2012.

Kaushik S., Singh A. K., Jigang W., Srikanthan T. Run-time computation and communication aware mapping heuristic for NoC based heterogeneous MPSoC platforms. In Proceedings of the 2011 Fourth International Symposium on Parallel Architectures, Algorithms and Programming, PAAP '11, (Washington, DC, USA), pp. 203–207, IEEE Computer Society, 2011.

Zhe L., Xiang L. NoC mapping based on chaos artificial bee colony optimization. In Computational Problem-Solving (ICCP), 2011 International Conference on, pp. 518 –521, oct. 2011.

Mandelli M., Amory A., Ost L., Moraes F. G. Multi-task dynamic mapping onto NoC-based MPSoCs. In Proceedings of the 24th symposium on Integrated circuits and systems design, SBCCI '11, (New York, NY, USA), pp. 191–196, ACM, 2011.

Habibi A., Arjomand M., Sarbazi-Azad H. Multicast-aware mapping algorithm for on-chip networks. In Proceedings of the 2011 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, PDP '11, (Washington, DC, USA), pp. 455–462, IEEE Computer Society, 2011.

Liu Y., Ruan Y., Lai Z., Jing W. Energy and thermal aware mapping for mesh-based NoC architectures using multi-objective ant colony algorithm. In Computer Research and Development (ICCRD), 2011 3rd International Conference on, vol. 3, pp. 407 –411, march 2011.

Zhong L., Sheng J., Jing M., Yu Z., Zeng X. , Zhou D. An optimized mapping algorithm based on simulated annealing for regular NoC architecture. In ASIC (ASICON), 2011 IEEE 9th International Conference on, pp. 389 –392, oct. 2011.

Sepulveda J., Strum M., Chau W. J., Gogniat G. A multiobjective approach for multi-application NoC mapping. In Circuits and Systems (LASCAS), 2011 IEEE Second Latin American Symposium on, pp. 1 –4, feb. 2011.

Sheng J., Zhong L., Jing M., Yu Z. , Zeng X. A method of quadratic programming for mapping on NoC architecture. In ASIC (ASICON), 2011 IEEE 9th International Conference on, pp. 200 –203, Oct. 2011.

Sangiovanni-Vincentelli A. Is a unified methodology for system-level design possible? IEEE Des. Test, vol. 25, pp. 346–357, July 2008.

Bonatti P. A., Lutz C., Murano A., Vardi M. ISO IEC 13818-2 MPEG2. Information Technology - Generic Coding of Moving Pictures and Associated Audio Information: Video," in ICALP 2006. LNCS, pp. 540–551, Springer, 2006.

Fan L. J., Li B., Zhuang Z. Q., Fu Z. Q. An approach for dynamic Hardware/Software partitioning based on DPBIL. In Proceedings of the Third International Conference on Natural Computation. Volume 05, ser. ICNC '07. Washington, DC, USA: IEEE Computer Society, 2007.

Bolanos F., Aedo J., Rivera F. System-level partitioning for embedded systems design using Population-based Incremental Learning. In CDES, H. R. Arabnia and A. M. G. Solo, Eds. CSREA Press, pp. 74–80, 2010.

White R. H. Competitive hebbian learning: Algorithm and demonstrations. Neural Networks, vol. 5, no. 2, pp. 261 – 275, 1992.

Thiele L., Bacivarov I., Haid W., Huang K. Mapping applications to tiled multiprocessor embedded systems. In Proceedings of the Seventh International Conference on Application of Concurrency to System Design, ser. ACSD '07. Washington, DC, USA: IEEE Computer Society, pp. 29–40, 2007.

Licencia

Derechos de autor 2014 DYNA

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.