Resumen

Presentamos un algoritmo heurístico para la distribución en tiempo de ejecución de conjuntos de tareas en una red en chip homogénea multiprocesador. El algoritmo está distribuido en los propios procesadores y, por lo tanto, puede aplicarse a sistemas de tamaño arbitrario. Además, las tareas añadidas en tiempo de ejecución pueden manejarse sin dificultad, permitiendo la optimización en línea. Basándose en información local sobre la carga de trabajo del procesador, el tamaño de la tarea, los requisitos de comunicación y la contención de enlaces, se toman decisiones iterativas sobre la migración de tareas a otros procesadores. Los resultados de mapeo para varios conjuntos de tareas de ejemplo se comparan primero con los de un algoritmo exacto (enumeración) con información global para una matriz de procesadores. Los resultados muestran que la calidad de mapeo lograda por nuestro algoritmo distribuido está dentro del 25% de la del algoritmo exacto. Para tamaños de matriz más grandes, se utiliza el recocido simulado como referencia y se investiga el comport

• Materias:Elementos lógicos Sistema de archivos Multinúcleo heterogéneo Flexibilidad del montium Gestión de memoria
• Subjects:Logic elements File system Heterogeneous multicore Montium flexibility Memory management
• Palabras claves:Algoritmo heurístico; Conjuntos de tareas; Red en chip multiprocesador; Algoritmo distribuido; Migraciones de tareas; Calidad de mapeo
• Keywords:Heuristic algorithm; Task sets; Multiprocessor network-on-chip; Distributed algorithm; Task migrations; Mapping quality