Resumen

Investigamos la complejidad y los resultados de aproximación en una red de procesadores en la que el retraso de la comunicación depende de la distancia entre los procesadores que realizan las tareas. A continuación, demostramos que no existe ninguna heurística con una garantía de rendimiento inferior a 4/3 para la minimización del tiempo de espera para el grafo de precedencia en una gran clase de redes de procesadores como el hipercubo, la red, el toro, etc., con un diámetro fijo δ∈ℕ. Ampliamos los resultados de complejidad cuando el grafo de precedencia es un grafo bipartito. También diseñamos un algoritmo eficiente de aproximación en tiempo polinómico O(δ2) para la minimización del tiempo de espera en redes de procesadores con diámetro δ.

• Materias:Algoritmos (Computadores) Lenguajes de programación (Computadores electrónicos) Algoritmos (Matemáticas) Matemáticas Redes multiclase
• Subjects:Computer algorithms Programming languages (Computer electronics) Agorithms (Math) mathematics Multiclass Networks
• Palabras claves:red de procesadores, minimización del makespan, grafo de precedencia, clase de procesadores, grafo bipartito, garantía de rendimiento, clase grande, resultados de complejidad, diámetro fijo, retardo de comunicaciones
• Keywords:processor network, makespan minimization, precedence graph, class of processor, bipartite graph, performance guarantee, large class, complexity results, fixed diameter, communications delay