Resumen

Analizamos un problema de programación de tareas en sistemas heterogéneos y proponemos un algoritmo de programación multipaso para resolverlo. Los algoritmos de programación existentes formulados como programación lineal entera 0-1 pueden utilizarse para considerar la optimalidad de la programación de tareas. Sin embargo, no pueden abordar relaciones complicadas entre tareas o costes de comunicación entre procesadores. Por lo tanto, proponemos un algoritmo de programación que formula los costes de comunicación como programación lineal entera 0-1. Por otro lado, la programación lineal entera 0-1 tarda mucho tiempo en calcular los resultados de la programación porque es NP-completa. Por tanto, también es necesario reducir el tiempo de programación. Una solución para reducir el tiempo de programación es la agrupación de grafos, que descompone un grafo de tareas grande en grafos de subtareas más pequeños (clusters). Además, es importante para el procesamiento paralelo y distribuido encontrar el paralelismo de tareas en un grafo de tareas. A continuación, también proponemos un algoritmo de clustering basado en SCAN. SCAN es un algoritmo para encontrar clusters en un grafo. El algoritmo de clustering basado en SCAN puede encontrar paralelismo de tareas en un grafo de tareas. Mediante ejemplos numéricos, argumentamos los dos puntos siguientes. En primer lugar, nuestro algoritmo de programación multipaso resuelve el problema de programación en sistemas heterogéneos. En segundo lugar, es superior a los algoritmos de programación existentes en términos de tiempo de cálculo.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:algoritmo de programación multipaso, escaneo, algoritmo, costes de comunicación, sistemas heterogéneos, programación lineal, algoritmos de programación, tiempo de programación, grafo de tareas, paralelismo de tareas
• Keywords:multistep scheduling algorithm, scan, algorithm, communication costs, heterogeneous systems, linear programming, scheduling algorithms, scheduling time, task graph, task parallelism