IIIIIIIIIIIIIIIIIIIII
Estrategias de asignación considerando la arquitectura
se utilizan después de haber sido previamente convertidos a TIGs mediante el algoritmoDSC.
Recordemos que el modelo basado en TIGs es un modelo simple donde no setiene en cuenta, por ejemplo, ninguna consideración sobre la existencia de dependenciasentre las distintas tareas. Esto podría provocar que la previsión hecha por la función decoste, entendida como una estimación teórica del tiempo de ejecución, no tuvieseninguna relación con los tiempos finalmente observados. O sea, en el supuesto másdesfavorable, el hecho de intentar minimizar la función descoste no supondría ningunagarantía para asegurar una mejora en el tiempo de ejecución, lo cuál nos llevaríanecesariamente a descartar totalmente el modelo de TIGs y las políticas de basadas enél. Por el contrario, con la realización de estas pruebas esperamos confirmar que entrevalores de función dé coste y tiempo de ejecución existe una correlación importante apesar de la existencia de parámetros no contemplados en el modelo como son lasdependencias entre tareas. Esto permitiría aceptar los resultados obtenidos por lasdistintas estrategias de mapping propuestas en este trabajo como punto de partida paralo que podría ser una extensión del modelo de TIGs y, por lo tanto, de las propiasestrategias de mapping con objeto de aumentar esa correlación.
No existe en la literatura ningún estudio parecido sobre la mencionada relación,que nosotros conozcamos, y no pretendemos tampoco realizar un estudio completo yexhaustivo que determine la influencia de todos los parámetros que pueden intervenir.Tal estudio daría lugar, sin duda, a un trabajo de una extensión comparable al actual.Las restricciones impuestas por las herramientas utilizadas, además, obligannecesariamente a considerar el presente estudio como una primera aproximación queconfirme, en cualquier caso, que existen fundados indicios para afirmar que existecorrelación entre función de coste y tiempo de ejecución y que permita, además,vislumbrar algunos de los factores a tener en cuenta para aumentar dicha relación.
Entorno de simulación
La experimentación realizada para intentar establecer la relación existente entrefunciones de coste y tiempo de ejecución se llevó a cabo en un entorno software que,originalmente, estaba orientado al estudio del problema del scheduling para DAGs concomunicaciones [Roi96]. Dicha aplicación permite, entre otras, realizar las siguientesoperaciones:
1. Proceso de asignación: permite calcular la asignación de las tareas de unDAG a un conjunto de procesadores utilizando la política ETF (Earliest Time
Simulación de la ejecución: partiendo de la asignación que proporciona elproceso descrito en el punto anterior, se realiza la simulación de la ejecuciónde un programa paralelo en el cual pueden haber cambiado los valores decómputo o de comunicación de las tareas respecto del grafo inicial. El modelode simulación usado solapa cómputo y comunicación.
142
IIIIIIIIIIIIIIIIIIIII
Estrategias de asignación considerando la arquitectura
En nuestro trabajo hemos utilizado únicamente la segunda función, añadiéndoleuna pequeña modificación que ha permitido introducir asignaciones calculadasexternamente para poder simular posteriormente la ejecución de un cierto grafoasignado de esa forma.
Así, para los grafos utilizados en nuestros experimentos se ha contadosimplemente con el tiempo de ejecución de esos grafos asignados mediante un métodomultietapa que incluía el algoritmo DSC orientado a DAGs y la estrategia de mappingpara TIGs usando la fase de contracción y la fase de asignación física.
En la figura 5.8 se muestra un esquema del conjunto de herramientas diseñadaspara la realización de esta experimentación:
• En primer lugar, se utiliza la herramienta que mediante el algoritmo DSCreduce un DAG a un TIG.
• En segundo lugar, se realiza la contracción del TIG anterior mediante losalgoritmos CA, CRM o CRME.
• En tercer lugar, mediante el algoritmo BOK_2 se calcula la asignación físicadel TIG contraído teniendo en cuenta el grafo de la arquitectura.
• En cuarto lugar, a partir de las salidas generadas por las tres herramientasanteriores, el programa asignador genera un conjunto de parejas nodo deDAG - procesador que se utilizan en el simulador para conocer la asignaciónde cada nodo del DAG original y realizar así la simulación.
• Por último, el simulador proporciona el tiempo de ejecución resultante de laejecución del DAG sobre la arquitectura especificada.
143
1
1M
DSC
CA/CRl
•|
T\/~\BO
1-
1•111
DAG
IT
(conversión DAG-TIG)
TIG« '
VI/CRME (contracción TIG)
TIG agrupado
EC_2 (asignación física)
*
f
•'
*
descripción
arquitectura
Estrategias de asignación considerando la arquitectura
descripción:
tarea TIG - grupo nodos DAG
descripción:
agrupación : grupo tareas TIG
parejas:
agrupación - procesador
_
- • :' ",
Asignador
parejas:
nodos DAG -procesador
• i / • • " • *
• SIMULADOR / E 1 11
1tiempo de ejecución
DAG
• Figura 5. 8 Entomo completo de asignación/simulación de DAGs
• Resultados experimentales
Para el desarrollo de este experimento se utilizaron el conjunto de grafos DAGs• que se presentaron en el capítulo 4, incluyendo además los grafos gl 1 y g 12, que fueron
excluidos del grupo de grafos irregulares porque su estructura era totalmente regular del_ tipo pipeline. Su inclusión en esta1 contar en los resultados información
regulares. La descripción concreta de
Nombre
I grafo
gil
experimentación resultaba interesante para podertanto de grafos puramente irregulares como grafosambos grafos se muestra en la tabla 5.6.
Tabla 5.6. Descripción de los grafos gl 1 y g!2Aplicación # nodos # nodos
DAG TIGAlgoritmo sistólico genérico del tipo "tiempo-espacio" 1026 32
_ g!2 Algoritmo sistólico para el cálculo del producto de 1026 32I
1
1
matrices
144
IIIIIIIIIIII
Estrategias de asignación considerando la arquitectura
IIIIIIII
Los grafos fueron contraídos y en la fase de asignación física se utilizó elalgoritmo BOK_2. Aunque ya hemos visto que los resultados de BOK_2 no son losmejores de entre todo el conjunto de heurísticas de asignación física, el objetivo de laexperimentación consiste en estudiar la posible correlación existente entre el valor de lafunción de coste obtenida por la aplicación de una cierta política de mapping y el tiempode ejecución del programa. Por lo tanto, no importa tanto la calidad de la heurística demapping como determinar la relación existente entre los dos términos mencionados.
Todos los grafos fueron simulados para las siguientes arquitecturas: totalmenteinterconectada, malla cerrada, hipercubo y anillo. El número de procesadores fue de 8,16 y 32 (a excepción de la malla donde se usaron 9 en vez de 8 procesadores).
A partir de los resultados obtenidos por el simulador del tiempo de ejecución decada uno de los grafos se pasó al análisis de la correlación existente entre ese valor y elvalor de la función de coste obtenido por la heurística de mapping.
El método tradicionalmente más utilizado para estudiar la correlación linealexistente entre dos conjunto de valores X = {xl5 x2,...xn} e Y = {yls y2,...,yn} entre loscuales se supone que existe una relación del tipo:
Y = (3X + e
lo constituye el cálculo del coeficiente de Pearman, r [Kot85]. Dicho coeficientese define como
r =
r es un índice adimensional acotado entre -1 y 1 que refleja el grado de relaciónlineal entre los dos conjuntos de datos (X e Y). Si r = 1, los pares de puntos (x¡, y¡) estándispuestos perfectamente sobre una recta de pendiente positiva; si r = -1 la pendiente dela recta es negativa. Cuando r = O no existe ninguna relación lineal entre ambosconjuntos de datos. Si O < | r | < 0.5 la relación lineal se considera débil, para 0.5 < | r | <0.8, la relación es moderada y para | r | > 0.8, la relación ya es fuerte [Dev87].
Asociado con el valor r, también suele manejarse el término r , conocido comocoeficiente de determinación, y que se puede interpretar como la proporción de lavarianza de y, que puede atribuirse a la varianza de x. El rango de r2 es O < r2 < 1, deforma que cuanto más próximo sea a 1, mayor será la dependencia de y atribuible a x.
La tabla 5.7 muestra los resultados obtenidos tanto de r como de r2 para elconjunto de grafos probados (los datos para su obtención se derivan de las tablas delApéndice E).
145
IIIIIIIIIII
Estrategias de asignación considerando la arquitectura
IIIIIIIII
Tabla 5.7. Valor de los coeficientes r y f¿ para tiempo de,ejecución y valor de función de coste
Grafo || gl
r li 0.87ti \ 0.75
g20.890.79
g30.850.72
§40.880.77
g50.510.26
g6-0.420.18
g70.740.55
g80.870.78
g90.50.25
gil0.990.99
g!20.990.99
En general, la correlación que se detecta es alta para 8 de los 11 casos, siendomás débil para los tres restantes (g5, g6 y g9). En una primera aproximación podríaargumentarse, que las razones que explican la baja correlación en los tres casosmencionados es el modelo utilizado en el simulador, donde cómputo y comunicacionesestán solapadas. Este modelo bajo el cual se realizaba la ejecución simulada de losgrafos contradice el modelo asumido por la función de coste minimax, donde lostérminos de cómputo y comunicación son aditivos, es decir, no existe concurrencia entreambas acciones.
Por otra parte, en el caso de los grafos gl l !y g 12, que son los que obtienen unacorrelación prácticamente igual a uno, es importante notar que su característica degrafos regulares formados por un conjunto de nodos conectados en forma de anillodonde cada uno de ellos internamente ejecuta una ristra secuencial de tareas que secomunican con tareas de su nodo vecino es lo que les convierte en grafos que encajanperfectamente con el modelo de ejecución supuesto para los TIGs y, en consecuencia,son los casos donde la correlación es máxima.
Los tiempos de ejecución obtenidos en las simulaciones suelen mostrar dosclaras tendencias. Por una parte, están aquellos grafos para los cuales el valor de lafunción de coste es mayoritariamente superior al tiempo de ejecución (gl, g2, g4, g5, g6g9 y g!2). En estos casos, durante la ejecución del programa se está aprovechando lasituación de concurrencia entre cómputo y comunicación. Por otra parte, existe otrogrupo diferenciado de grafos para los que el tiempo de ejecución es superior a la funciónde coste (g3, g7, g8 y gl 1). En estos casos, la existencia de determinadas dependenciasentre los nodos del grafo DAG provocan la aparición de una serie de retrasos que desdeel punto de vista de los nodos receptores tienen una influencia equivalente al volumende comunicaciones considerado en la función de coste. De todas formas, aunque en unoscasos la existencia de las dependencias quede oculta o sea patente en función del valorfinal de los tiempos de ejecución, es importante notar que su influencia siempre es iguala pesar de que la agrupación de los nodos del grafo TIG sea distinta ya sea con 8, 9, 16o32 procesadores. Es decir, las dependencias existen pero el hecho de que la política demapping no las considere y decida agrupar las tareas de un modo u otro en función delnúmero de procesadores no repercute en una variación en la relación final entre funciónde coste y tiempo de ejecución para un determinado grafo.
Analizando los tres casos donde la correlación entre tiempo de ejecución yfunción de coste es más débil se observa que la baja correlación se debe a la existenciaen el grafo contraído de algún nodo que está conectado con todos los demás y quedetermina el valor de la función de coste. La fase de asignación física conlleva siempreun incremento de la función de coste debido al incremento de las comunicaciones de esenodo. Sin embargo, durante la ejecución simulada la ocurrencia en paralelo de cómputoy comunicaciones permite que los tiempos de ejecución no crezcan en la mismaproporción que lo hace la función de coste.
146
IIIIIIII
IIIIIII
IIII
Estrategias de asignación considerando la arquitectura
Este fenómeno puede sugerir que el uso de la función de coste minimax cuandose produce un solapamiento en los términos que ella supone secuenciales no es el tipode estimador más preciso. Podríamos pensar en este caso que dado el solapamiento entrecómputo y comunicaciones, éste segundo término no va a ser muy influyente y que eltiempo de ejecución va a depender directamente sólo del volumen de cómputo máximoentre los distintos procesadores. Partiendo de esta hipótesis se calculó los coeficientesde correlación y determinación para todos los grafos usando como variableindependiente (X) el volumen máximo de cómputo que presenta una cierta asignación ycomo variable dependiente (Y) el tiempo de ejecución. Los resultados aparecen en latabla 5.7.
Tabla 5.7. Valor de los coeficientes r y r2 para tiempo de ejecución y volumen máximo decómputo
Grafor2
gi0.79 •0.62
g20.930.86
g30.990.98
g4-0.420.18
g50.920.85
g60.880.79
-g70.200.04
g80.980.96
g90.990.99
gil0.990.99
g!20.990.99
Como se ve, el índice de correlación en este caso supone un ligero aumento enciertos casos, mejorando en concreto los tres supuestps que en el caso anterior teníanuna correlación más débil, aunque aparecen dos casos que empeoran de formaconsiderable (g4 y g7). El volumen de cómputo máximo, pues, no parece ser tampoco elfactor que determine el valor del tiempo de ejecución.
El siguiente paso natural, pues, sería establecer un modelo de correlación máscomplejo que tuviese en cuenta ambas variables. Así, si la variable Y fuese el tiempo deejecución, el modelo probabilístico que la relacionaría con las dos variables X] (valor dela función de coste) y X2 (volumen máximo de cómputo) sería del tipo:
En este caso, los resultados obtenidos para los coeficientes de correlaciónmúltiple, R, y de determinación múltiple, R2, se reflejan en la tabla 5.8.
Tabla 5.8. Valor del coeficiente de correlación múltiple, R, y de determinación múltiple, R¿, paratiempo de ejecución, función de coste y volumen máximo de cómputo
GrafoRR¿
gl0.970.95
g20.970.94
g30.990.99
g40.880.78
g50.940.89
g60.890.80
g70.740.55
g80.990.99
g90.990.99
gil0.990.99
g!20.990.99
Los resultados reflejados en la tabla confirman que el modelo propuesto es elque mejor permite estimar el valor del tiempo de ejecución a partir de los valoresconocidos de la función de coste y del volumen de cómputo máximo en el supuesto dedisponer de un sistema donde cómputo y comunicaciones ocurran solapadamente.
Además, nos permite también detectar un conjunto de situaciones para las cualesla estrategia de asignación CRME tiene un comportamiento anómalo. Son todosaquellos casos donde existe un cierto nodo con un elevado número de arcos y, por lo
147
IIIIIIIIIIIIIIIIIIIII
Estrategias de asignación considerando la arquitectura
tanto, con un elevado coste de comunicación que va a determinar el valor de la funciónde coste final y que provocará que, durante los sucesivos pasos de agrupación, se vayaformando alguna agrupación con un volumen de cómputo muy elevado. Esto provocaráque, al final, el grafo contraído presente un gran desequilibrio en el reparto de cómputo.El valor de la función de coste vendrá determinado por el nodo con el elevado volumende comunicación, pero la estrategia, ante la imposibilidad de reducir dicho coste, sehabrá limitado a agrupar nodos sin importarle que eso provoque un gran desequilibriode cómputo. Durante la ejecución, el tiempo final vendrá determinado por aquel nodocon un gran desbalanceo de cómputo (ya que las comunicaciones tenderán a solaparse).En consecuencia, para estos casos la correlación correcta se da entre volumen máximode cómputo y tiempo de ejecución.
La solución para estos casos consiste en incluir en la fase de agrupación (CA) unmecanismo adicional que durante los sucesivos pasos de agrupamiento detecte laexistencia de un nodo con las características mencionadas. A partir del momento en quese detecta la presencia de dicho nodo, la agrupación del resto de nodos se debe realizarbuscando el equilibrio de cómputo entre las agrupaciones resultantes en vez de guiarsepor el valor mínimo de cost_merg¡j.
En resumen, podemos concluir que los resultados de correlación entre tiempo deejecución y función de coste son buenos para los casos estudiados, donde se usó unsimulador en el que existía solaparniento entre comunicación y cómputo, y se simuló elconjunto de 11 grafos mencionado. De tal experimentación se ha deducido un parámetroadicional que influye en el tiempo de ejecución final en el tipo de sistema simulado y seha propuesto un mecanismo para corregir, en estos casos, las heurísticas basadas en lafunción de coste minimax.
148
IIIIIIIIIIIIIIIIIIIII
Conclusiones y líneas abiertas
Conclusiones y líneas abiertas
En el presente trabajo se ha presentado un conjunto de estrategias de propósito general pararesolver de forma eficiente el problema del mapping en sistemas paralelos basados en paso demensajes. Para ello ha sido necesario: ,
• Realizar un estudio de las distintas soluciones presentes en la literatura para la resolucióndel mencionado problema. Este estudió se acompañó de una evaluación de los distintosmodelos que se adoptaban en esas soluciones, estudio que permitió escoger aquel modeloque mejor se correspondía con las características de las aplicaciones paralelas que sepretenden asignar.
• Realizar un estudio detallado _de aquellas estrategias de asignación que utilizaban elmismo modelo adoptado en nuestro trabajo. El estudio se centró especialmente enaquellas metodologías que no estaban orientadas a un tipo de aplicación o de arquitecturaen concreto. Se analizó también los inconvenientes que presentaban dichas estrategias olas posibles situaciones en las que eran susceptibles de mejora.
• Realizar un estudio de las principales funciones objetivo propuestas en la resolución delproblema del mapping con objeto de escoger aquella que más se aproximaba al modelode arquitectura paralela para el que estaba orientada la estrategia de asignación.
• Diseñar una nueva estrategia heurística de tipo mixto que incorpora en su fase greedy(denominada CA: Clustering Algorithm) aquellas características que habíamosidentificado como más interesantes para encontrar asignaciones que consiguiesen unareducción de las comunicaciones presentes en el programa, al tiempo que se intentabaequilibrar el trabajo total entre todos los procesadores del sistema (entendiendo portrabajo total, tanto el cómputo como las comunicaciones que realizan las tareas). Además,la fase greedy sigue un proceso de agrupación de tareas que permite llegar a una situacióndonde el programa puede quedar reducido a un número de agrupaciones menor que elnúmero de procesadores, eliminando así aquel paralelismo que pudiera ser inútil teniendoen cuenta las comunicaciones involucradas en él. Como fase iterativa para refinar losresultados generados en la primera fase de la heurística se han diseñado dos alternativas:un método de baja complejidad basado en el movimiento de tareas individuales(denominado CRM: Clustering and Reassignment by Movements) y un método de mayorcomplejidad basado en el intercambio de tareas (denominado CRME: Clustering andReassignment by Movements and Exchanges).
149
IIIIIIIIIIIIIIIIIIIII
Conclusiones y líneas abiertas
• Diseñar una extensión de la heurística con objeto de poderla aplicar en aquellos sistemascon una arquitectura cuyos procesadores no estuviesen totalmente interconectados y que,por consiguiente, implicasen la necesidad de considerar el parámetro de la distancia entreprocesadores. Las extensiones que se realizaron (denominadas estrategias de asignaciónfísica) supusieron la adaptación y combinación de algunos métodos clásicos usados en laresolución del problema del mapping en su versión 1 a 1.
A partir del conjunto de heurísticas diseñadas se realizó una experimentación exhaustiva conobjeto de validar su efectividad en la resolución del problema del mapping. El conjunto deexperimentos realizados fue:
• Comparar la heurística con un método óptimo en el supuesto de arquitecturas totalmenteinterconectadas. El conjunto de grafos cubría un amplio espectro por lo que se refiere a laregularidad de su estructura, granularidad y grado de conectividad. Los resultadosobtenidos en esta comparación permitieron concluir que la heurística en sus versionesCRM y CRME obtenía soluciones muy próximas al valor óptimo.
• Comparar la heurística con otros métodos de la literatura (greedy, iterativos y mixtos). Seusó un conjunto de grafos de mayor tamaño que en el caso anterior lo que permitióevaluar también la relación que presentaban los diferentes métodos entre calidad de lasolución y tiempo de ejecución para su obtención. De esta comparación se concluyó quela versión CRM era el método que presentaba el mejor compromiso entre ambos factores:sus soluciones eran comparables, e incluso superiores, a las de métodos iterativos máscostosos eomputacionalmente como Simulated Annealing, peor el tiempo paraconseguirlas era ligeramente superior al de las estrategias greedy. La experimentaciónrealizada permitió también validar una cota propuesta para estimar el número demovimientos que realiza la fase iterativa del método cuando el grafo asignado tiene unaestructura regular.
• Comparar los distintos métodos propuestos para la resolución del problema del mappingcon arquitecturas no totalmente interconectadas Se evaluó el incremento queexperimentaba, por una parte, la función de coste y, por otro, el volumen total decomunicaciones. De los resultados se dedujo que la estrategia denominada MOVIM era laque presentaba el mejor compromiso entre calidad de las soluciones y tiempo decómputo. Dicha estrategia consiste en la concatenación del método CRM, seguido de unalgoritmo de incrustación, un algoritmo iterativo y una última fase de refinamiento basadaen movimientos individuales de tareas. De la experimentación se comprobó que aquellosgrafos que presentaban una granularidad media eran los que mayores incrementos teníanen la función de coste.
• Formular y validar dos cotas teóricas que permiten estimar a priori el incremento de lafunción de coste y del volumen de comunicación cuando se aplican las estrategias deasignación física a partir de un programa asignado previamente a una arquitecturatotalmente interconectada.
• Comprobar el grado de correlación existente entre los valores que presenta la función decoste y el tiempo de ejecución de una cierta aplicación en un sistema paralelo que solapatotalmente cómputo y comunicaciones en la ejecución de los programas. Se constató queexiste un grado elevado de correlación para la mayoría de los grafos analizados. Se
150
IIIIIIIIIIIIIIIIIIIII
Conclusiones y líneas abiertas
propusieron también posibles mejoras en la estrategia de asignación para aumentar elgrado de correlación en aquellos casos analizados en los que ésta era más débil.
Habiéndose demostrado experimentalmente la bondad de la estrategia de asignaciónpropuesta, las principales líneas abiertas a partir de este trabajo son:
• Probar la estrategia para realizar la asignación de aplicaciones reales en sistemas paralelosy analizar la posible influencia de factores no contemplados en el modelo de grafo TIG yen la función de coste utilizada. Por ejemplo, la existencia de dependencias temporalesentre procesos, la influencia del tipo de primitivas para el paso de mensajes(bloqueantes/no bloqueantes), el grado de solapamiento entre cómputo y comunicaciónexistente en el computador paralelo.
• Estudiar la influencia de la precisión de los valores de los parámetros usados en el modeloTIG (volumen de cómputo de los nodos y volumen de comunicación de los arcos) en lacalidad de las asignaciones obtenidas por las estrategias de mapping y su repercusión enlos tiempos de ejecución.
151
111111
1•
1•
11
11111
[Age95]
[AH93]
[A1M90]
[And91]
[Ant91]
[App89]
[Avr94]
[Bac90]
[Bal89]
[Ban93]
Referencias
Referencias
T. Agerwala et alter, "SP2 system architecture", IBM Systems Journal, Vol.34, no. 2, pp. 152-184,1995.
H. Ali and H. El-Rewini, "Task allocation in distributed systems: a split-graph model", J. of Combinatorial Mathematics, and Combin. Computing,Vol. 14, pp. 15-32,1993.
M. Al-Mouhammed, "Lower bound on the number of processors and time forscheduling precedence graphs with communication costs", IEEE Trans.Softw. Eng., Vol. SE-16, no. 12, pp. 1390-1401, 1990.
G. R. Andrews, "Paradigms for process interaction in distributed programs",ACM Còmput. Surveys, Vol. 23, no. 1, pp. 49-90, 1991.
S. Antonelli et alter, "Modeling concurrent programs for static mapping",Proc. of Parallel Computing '91 (London, UK), Elsevier, NY, pp. 357-366,1991. i i
W. F. Appelbe, K. Smith and C. McDowell, "Start/Pat: a parallelprogramming toolkit", IEEE Software, Vol. 6; no. 4, pp. 29-38, Jul. 1989.
G. S. Avrunin et alter, "Automated derivation of time bounds in uniprocessorconcurrent systems", IEEE Trans, on Soft. Engineering, Vol. 20, no. 9, pp.708-719, Sep. 1994.
F. Baccelli and Z. Liu, "On the execution of parallel programs onmultiprocessor systems - a queueing theory approach", J. ACM, Vol. 37, no.2, pp. 373-414, 1990.
H. E. Bal, J. G. Steiner and A. S. Tanenbaum, "Programming languages fordistributed computing systems", ACM Comp. Surveys, Vol. 31, no. 3, pp.261-322, 1989.
U. Banerjee, R. Eigemann, A. Nicolau and D. A. Padua, "Automatic ProgramParallelization", Proc. of the IEEE, Vol. 81, no. 2, pp. 21 1-243, 1993.
152
I
I
Referencias
II
[Ber87] F. Herman and L. Snyder, "On mapping parallel algorithms into parallelI architectures", J. Parall. Distrib. Còmput., Vol. 4, no. 5, pp. 439-458, 1987.
_ [Ber94] F. Herman and B. Stramm, "Mapping function-parallel programs with theI Prep-P automatic mapping preprocessor", Tech. Report No. CS94-397
University of California, San Diego. Reimpreso en "Scheduling and load
•
balancing in parallel and distributed systems", IEEE Comp. Society Press,pp. 256-283, 1995.
I
|[Bok81b] S.H. Bokhari, "A shortest tree algorithm for optimal assignments across
space and time in a distributed processor system", IEEE Trans. SoftwareEng., vol. SE-7,no. 6, pp. 335-341, Nov. 1981.
* [Bop91] R. V. Boppana and C. S. Raghavendra, "Generalized schemes for access andalignment of data parallel procesors with self-routing interconnection
I networks", J. Parallel and Distr. Comp., Vol. 1 1, pp. 97-1 11, 1991.
_ [Bou95] P. Bouvry, J. Chassin de Kergommeaux and D. Trystram, "Efficient solutionsI for mapping parallel programs", Proc. of EuroPar'95, Springer- Verlag, pp.
379-390, 1995.
| [Bul92] T. Bultan and C. Aykanat, "A new mapping heuristic based on Mean FieldAnnealing", Journal of Parall. and Distrib. Computing, Vol. 16, pp. 292-305,1992.
[BokSla] S. H. Bokhari, "On the mapping problem", IEEE Trans, on Computers, Vol.C-30, no. 3, pp. 207-214, Mar. 1981.
[Car85] M. J. Carey, M. Livny and H. Lu, "Dynamic task allocation in a distributeddatabase sy291, 1985.•database system", 5th Int. Conf. on Distributed Computing Systems, pp. 282-
I [Cas88] T. L. Casavant and J. G. Kuhl, "A taxonomy of scheduling in general-* purpose distributed computing systems", IEEE. Trans. Software Eng., vol.
SE-14,no. 2, pp. 141-154, Feb 1988.
[Cha91] K. M. Chandy and C. Kesselman, "Parallel programming in 2001", IEEE_ Software, pp. 1 1 -20, Nov. 1 99 1 .
[Chan94] R. Chandrasekharam, V. V. Vinod and S. Subramanian, "Genetic algorithmfor emmbedding a complete graph in a hypercube with a VLSI application",Microprocessing and Microprogramming, Vol. 40, pp. 537-552, 1994.I
|[Chau93] V. Chaudhary and J. K. Aggarwal, "A generalized scheme for mapping
parallel algorithms", IEEE Trans, on Parall. and Distrib. Systems, Vol. 4, no.3, pp. 328-346, Mar. 1993.
153
111
111
111•
1
1•
111
[Cho82]
[ChuSO]
[Chu84]
[Cof73]
[Cof76]
[Con67]
[Cor92]
[Dev87]
[Efe82]
[E1R90]
[E1R94]
[Ens78]
[Erc90]
[Eva84]
Referencias
T. C. K. Chou and L A. Abraham, "Load balancing in distributed systems",IEEE Trans. Software Eng., Vol. SE-8, no. 4, pp. 401-412, Jul. 1982.
W. Chu, L. Holloway, M.T. Lan and K. Efe, "Task allocation in distributeddata processing", Computer, Vol. 13, no. 11, pp. 57-69, Nov. 1980.
W. Chu, M. T. Lan and J. Hellerstein, "Estimation of intermodulecommunication (IMC) and its applications in distributed processing systems",IEEE Trans. Còmput., Vol. C-33, no. 8, pp. 691-699, 1984.
E. G. Coffman and P. J. Denning, "Operating System Theory", EnglewoodCliffs, NJ:Prentice-Hall, 1973.
E. G. Coffman, "Computer and job-shop scheduling theory", John Wiley,NY, 1976.
R. W. Conway, W. L. Maxwell and W. L. Miller, "Theory of Scheduling",Reading; MA: Addison- Wesley, 1967.
A. Cortés, "La asignación dinámica de tareas en computadores paralelos: unanálisis crítico", Trabajo experimental, Universidad Autónoma de Barcelona,1992.
J. L. Devore, "Probability and Statistics for Engineering and the Sciences(2nd. edition)", Monterey, California, Brooks/Cole Publishing Company,1987.
K. Efe, "Heuristic models of task assignment scheduling in distributedsystems", IEEE Computer, Vol. 15, no. 6, pp. 50-56, Jun. 1982.
H. El-Rewini and T. Lewis, " Scheduling parallel program tasks onto arbitraytarget machines", J. Parall. Distrib. Còmput., Vol. 9, no. 2, 138-153, 1990.
H. El-Rewini, T. G. Lewis and H. H. Ali, "Task scheduling in parallel anddistributed systems", Englewood Cliffs, NJ: Prentice-Hall, 1994.
P. H. Enslow jr., "What is a "distributed" data processing system", Computer,Vol. 11, no. l,pp. 13-21, Jan. 1978.
F. Ercal, J. Ramanujam and P. Sadayappan, "Task allocation onto ahypercube by recursive mincut bipartitioning", J. Parall. and Distrib.Còmput., Vol. 10, pp. 35-44, 1990.
J. R. Evans el al., "Applied production and operations management", St.Paul, MN: West, 1984.
154
111•
1̂v
111•
1•
11
1•
1M1
1I
1
[Fer73]
[Fid82]
[Fly96]
[Fox89]
[Gab82]
[Gar79]
[Ger92]
[Ger93]
[Gir88]
[Gra69]
[Gra79]
[Her91]
[Hou90]
Referencias
E. Fernandez and B. Bussell, "Bounds on the number of processors and timefor multiprocessor optimal schedules", IEEE Trans Còmput., Vol. C-22, no.8, pp. 745-751.
C. M. Fiduccia and R. M. Mattheyses, "A linear-time heuristic for improvingnetwork partitions", Proc. 19th Design Automation Conference, pp. 175-181,June 1982.
M. J. Flynn and K. W. Rudd, "Parallel Architectures", ACM Comp. Surveys,Vol. 28, no. 1, pp. 67-70, March 1996.
G. Fox, "Parallel computing comes of age", Concur. Pract. Exp., Vol. 1, no.l,pp.63-103, 1989.
A. Gabrielian and D. B. Tyler, "Optimal object allocation in distributedcomputer systems", Proc. 4th Int. Conf. Dist. Comp. Systems, pp. 84-95,May 1984.
M. Garey and D. Johnson, "Computers and intractability", W. H. Freemanand Co., San Francisco, 1979.
A. Gerasoulis and T. Yang, "A comparison heuristic for scheduling directedacyclic graphs on multiprocessors", Journal of Parall. and Distrib. Còmput.,Vol. 16, pp. 276-29 1,1 992.
tA. Gerasoulis and ,T. Yang, "On the granularity and clustering of directedacyclic graphs", IEEE Trans. Parallel and Dist. Syst, Vol. 4, no. 6, pp. 686-701, Jun. 1993.
M. Girkar and C. Polychronopoulos, "Partitioning programs for parallelexecution", Comm. ACM, pp. 216-229., 1988. ???
R.Graham, "Bounds on multiprocessing timing anomalies", SIAM, J. Appl.Math., Vol. 17, No. 2, pp. 416-429, 1969.
R. Graham, E. Lawler, J. Lenstra and A. Rinnooy Kan, "Optimization andapproximation in deterministic sequencing and scheduling, a survey", Ann.Disrc. Math., Vol. 5, pp. 236-287, 1979.
P. Hernández, "Políticas de scheduling estático para sistemasmultiprocesador", Tesis Doctoral, Universidad Autónoma de Barcelona,octubre 1991.
C. Houstis, "Module allocation of real-time applications to distributedsystems", IEEE Trans. Softw. Eng., Vol. SE-16, no. 7, pp. 699-709, 1990.
155
111•
1̂B
1'
1
1•
1
1
1
1
1
1
1
1
1
1
[Hwa89]
[Kas84]
[Kho74]
[Kim88]
[Kit93]
[Kle81]
[Kot85]
[Kua88]
[Laa87]
[Lee87]
[Lee92]
[Lew92]
[Lew93]
Referencias
J.-J. Hwang, Y.-Ch. Chow, F. D. Anger and Ch.-Y. Lee, "Schedulingprecedence graphs in systems with interprocessor communication times",SIAM J. Còmput., pp. 244-257, 1989.
H. Kasahara and S. Narita, "Practical multiprocessor scheduling algorithmsfor efficient parallel processing", IEEE Trans. Comp., Vol. C-33, no. 11, pp.1023-1029, Nov, 1984.
W. H. Kholer and K. Steiglitz, "Characterization and theoretical comparationof branch and bound algorithms for permutation problems", J. Còmput.Mach., Vol. 21, pp. 140-156, Jan, 1974.
S. J. Kim and J. C. Browne, "A general approach to mapping of parallelcomputation upon multiprocessor architectures", Int'l Conf. on ParallelProcess., Vol. 3, pp. 1-8, 1988.
J. P. Kitajima, C. Tron and B. Plateau, "ALPES: a tool for the performanceevaluation of parallel programs", Environments and tools for parallelscientific computing (Jack Dongarra and Bernard Tourancheau editors),North-Holland: Amsterdam, pp. 213-228, 1993.
L. Kleinrock and A. Nilsson, "An optimal scheduling algorithms for time-shared systems", J. ACM, Vol. 28, no. 3, pp. 477-486, Jul. 1981.
C. R. Kothari, "Research methodology", Wishwa Prakashan, New Delhi,1985.
B. Kruatrachue and T. Lewis, "Grain size determination for parallelprogramming", IEEE Software, Vol. 1, no. 5, pp. 97-106, 1988.
P.J.M. van Laarhoven and E.H.L. Aarts, "Simulated Annealing: Theory andApplications", D: Reidel Publishing Company, 1987.
S. Lee and J. Aggarwal,- "A mapping strategy for parallel computing", IEEETrans. Còmput., Vol. C-36, no. 4, pp. 433-442.
C. Lee, D. Lee and M. Kim, " Optimal task assignment in linear arraynetworks", IEEE Trans. Còmput., Vol. 41, no. 7, pp.877-880, 1992.
T. Lewis and H. El-Rewini, "Introduction to Parallel Computing",Englewood Cliffs, NJ:Prentice-Hall, 1992.
T. Lewis and H. El-Rewini, "Parallax: a tool for parallel programscheduling", IEEE Parallel and Distr. Technology, Vol. 1, no.2, pp.62-72,May 1993.
156
111•
1•
1111•
1•
11
1
1
111
[Liv82]
*
[Lo88a]
[Lo88b]
[Lo91]
[Lo92]
[Luq90]
[Luq93]
[Luq95]
[Luq96]
[Ma82]
[Mar93]
[May93]
Referencias
Livny and Melman, "Load balancing in homogeneous broadcast distributedsystems", Proc. ACM Computing Network Performance, pp. 44-55, Symp1982.
V. M. Lo, "Heuristic algorithms for task assignment in distributed systems",IEEE Trans. Còmput., Vol. 37, no. 1 1, pp. 1384-1397, 1988.
V. M. Lo, "Algorithms for static assignment and symmetric contraction indistributed computing systems", Proc IEEE Int. Conf. on Parallel Proc., pp.239-244, 1988.
V. M. Lo et alter, "OREGAMI: tools for mapping parallel computations toarchitectures", Int'l J. of Parallel Programming, Vol. 20, no. 3, pp. 237-270,1991.
V. Lo, "Temporal communication graphs: Lamport's process-time graphsaugmented for the purpose of mapping and scheduling", J. of Parallel andDistrib. Còmput, Vol. 16, pp. 378-385, 1992.
E. Luque, A. Ripoll, P. Hernández and T. Margalef, "Impact of taskduplication on static-scheduling performance in multiprocessor systems withvariable execution time tasks", ACM Computer Architecture News(SIGARCH), 1990 Int. Conf. on Supercomputing, Vol. 18, pp.43 9-446, 1990.
E. Luque, A. Ripoll, T. Margalef and P. Hernández, "Static scheduling ofparallel program graphs including loops", Proc. Int. Conf. on System ScienceHICCS-96, IEEE CS Press, Vol. II, , pp. 526-535, 1993.
E. Luque, A. Ripoll, A. Cortés and T. Margalef, "A distributed diffusionmethod for dynamic load balancing on parallel computers", Proc. of theEuromicro Workshop on Parall. and Dist. Proc., IEEE CS Press, pp. 43-50,1995.
E. Luque et alter, "PSEE: a tool for parallel systems learning", Computer &Artificial Intelligence, Vol. 14, no. 1, pp. 319-339, 1996.
*•
P. Ma, E. Lee and M. Tsuchiya, "A task allocation model for distributedcomputing systems", IEEE Trans, on Computers, Vol. 1, pp. 41-47, 1982.
T. Margalef, "Scheduling de programas paralelos con un comportamientodinámico", Tesis Doctoral, Universidad Autónoma de Barcelona, Octubre1993.
M. D. May, P. W. Thompson and P. H. Welch, "Networks, routers andtransputers: function, performance and applications", IOS Press: Amsterdam,The Netherlands, 1993.
157
I
II
Referencias
II —
[McG89] C. McGreary and H. Gill, "Automatic determination of grain size for efficient
•parallel programming", Commun. ACM, Vol. 32, no. 9, pp. 1073-1078, Sep.1989.
I [Ma82] P.Y.R. Ma, E. Y. S. Lee and J. Tsuchiya, "A task allocation model fordistributed computing systems", IEEE Trans. Còmput., vol. C-31, no. 1, pp.
- 41-47, Jan. 1982.
[Mun69] R. R. Muntz and E. G. Coffman, "Optimal preemtive scheduling on two
I
|
[Nor93] M. G. Norman and P. Thanisch, "Models of machines and computation formapping in multicomputers", ACM Comp. Surveys, Vol. 25, no. 3, pp. 263-,Sep. 1993.
• [OH93] I. Oliver, "Programming classics: implementing the world's best algorithms",NY: Prentice-Hall, 1993.
[OusSO] J. Ousterhout, D.Scelza adn P. Sindhu, "Medusa: an experiment in distributed_ operating system structure", Comm. ACM, Vol. 23, No. 2, pp. 92-105, Feb.I 1980.
|
[Pan90] C. M. Pancake and D. Bergman, "Do parallel languages respond to the needsof scientific programmers?", IEEE Computer, pp. 13-23, Dec. 1990.
procesor system", IEEE Trans. Computers, Vol. C-18, no. 11, pp. 1014-1020,Nov. 1969.
[Pan91] C. M. Pancake, "Software support for parallel computing: where are weheaded?", Comm. of the ACM, Vol. 34, no. 11, pp. 53-64, Nov. 1991.
[Pap82] C. H. Papadimitrou and K. Steiglitz, "Combinatorial optimization: algorithmsand complexity", Prentice-Hall, 1982.
I [Pea91] D. Pease et alter, "PAWS: a performance evaluation tool for parallel• computing systems", Computer, Vol. 24, no. 12, pp. 18-28, Jan. 1991.
I [Pol89] C. D. Polychronopoulus et alter, "Parafrase-2: an environment forparallelizing, partitioning, synchronizing and scheduling programs on
Imultiprocessors", Proc. Int'l Conf. Parallel Proc., Vol. 2, Perm. StateUniversity, pp. 39-48, 1989.
|
[Qin91] B. Qin, H. A. Sholl and R. A. Ammar, "Micro time cost analysis of parallelcomputations", IEEE Trans, on Computers, Vol. 40, no. 5, pp. 613-628, May1991.
I [Qui87] M. Quinn, "Designing efficient algorithms for parallel computers", NewYork: McGraw-Hill, 1987.
I
158
111•
1̂B
1
1I•
1•i
1
1
1
1
[Ram72]
[Ram88]
[Roi96]
[Sad87]
[Sad90]
[Sar89]
[Sch70]
[Sel92]
[Sen96]
[Sen97]
[Sha90]
[She85]
Referencias
C. V. Ramamoorthy, K. M. Chandy and J. L. González, "Optimal schedulingstrategies in a multiprocessor system", IEEE Trans, on Comp., Vol. C-21, pp.137-146, Feb. 1972.
J. Ramanujam, F. Ercal and P. Sadayappan, "Task allocation by simulatedannealing", Proc. Int'l Conf. on Supercomputing, Boston, MA, Vol. 3, pp.471-480, 1988.
C. Roig, "Algoritmos de planificación para grafos de precedencia conretardos de comunicación y tiempos variables", Trabajo experimental,Universidad Autónoma de Barcelona, Julio, 1996.
P. Sadayappan and F. Ercal, "Nearest-neighbor mapping of finite elementgraphs onto processor meshes", IEEE Trans. Còmput, Vol 36, no. 12,pp. 1408- 1424, Dec. 1987.
P. Sadayappan, F. Ercal and J. Ramanujam, "Cluster partitioning approachesto mapping parallel programs onto a hypercube", Parallel Computing, Vol.13, pp. 1-16, 1990.
V. Sarkar, "Partitioning and scheduling parallel programs formultiprocessors", Pitman, London, 1989. ••
L. Schrage, "Solving resource-constrained network problems by implicitenumeration preemptive case", Oper. Res., Vol. 18, pp. 263-278, Mar. 1970.
S. Selvakumar and C. Silva Ram Murthy, " An efficient heuristic algorithmfor mapping parallel programs onto multicomputers", Microprocessing andMicroprogramming, Vol. 36, pp. 83-92, 1992/1993.
M. A. Senar, A. Cortés, A. Ripoll, and E. Luque, "A clustering-reassigningstrategy for mapping parallel programs", artículo aceptado en 8th IASTEDInt. Conf. on Parallel and Distributed Computing and Systems, Chicago,1996.
M. A. Senar, A. Ripoll, A. Cortés and E. Luque, "An efficient clustering-based approach for mapping parallel programs", artículo aceptado en 5thEuromicro Workshop on Parallel and Distributed Processing, Londres , Enero1997.
A. C. Shaw, "Deterministic timing schema for parallel programs", TR #90-05-06, Dept. of Computer Science and Engineering, University ofWashington, September, 1990.
C.-C. Shen and W.-H. Tsai, "A graph matching approach to optimal taskassignment in distributed computing systems using a minimax criterion",IEEE Trans. Computers, Vol. C-34, no. 3, pp. 197-203, Mar. 1985.
159
Referencias
II
[Shi90] B. Shirazi, M. Wang and G. Pathak, "Analysis and evaluation of heuristic
•methods for static task scheduling", Journal Parall. Distrib. Comp., Vol. 10,pp. 222-232, 1990.
I [Shi94] B. Shirazi et alter, "PARSA: a PARallel program Scheduling andAssessment tool", Proc. 1994 Symp. Assessment of Quality Software
_ Development Tools, IEEE CS Press, Los Alamitos, Calif., pp. 96-111,1994.
[Sta84] J. A. Stankovic and I. S. Sidhu, "An adaptive bidding algorithm for
I processes, clusters and distributed groups", Proc. 4th Int. Conf. Dist. Comp.Systems, pp. 49-59, May 1984.
|
[Sto77] H. S. Stone, "Multiprocessor scheduling with the aid of network flowalgorithms", IEEE Trans. Software Eng., vol. SE-4, pp. 85-93, 1977.
|[Sto78] H. S. Stone, "Critical load factors in two-processor distributed systems",
IEEE Trans. Software Eng., vol. SE-4, no. 3, pp. 254-258, May 1978.
I [Stu95] C. B. Stunkel et alter, "The SP2 high-performance switch", IBM Systems• Journal, Vol. 34, no. 2, pp. 185-204, 1995.
I [Sup96] R. Suppi, "Modelado y simulación de sistemas paralelos", Tesis Doctoral,Universidad Autónoma de Barcelona, Junio 1996.
| [Tal93] E-G. Talbi and T. Muntean, "General heuristics for the mapping problem",Transputer Applications and Systems '93, Vol. 2, pp. 1229-1241, 1993.
| [Thu92] R. Thurimella and Y. Yesha, "A scheduling principle for precedence graphswith communication delay", Proc. Int. Conf. Parall. Proc., CRC Press, Vol.
• III, pp. 229-236, 1992.
[Tsi74] D. C. Tsichritzis and,P. A. Bernstein, "Operating Systems", New York:I Academic, 1974.
m [Vel90] B.Veltman, B.Lageweg and J. Lenstra, '.'Multiprocessor scheduling withI communication delays", Parallel Còmput., Vol. 16, no. 2-3, pp. 173-182," 1990.
g [Wan85] Y. Wang, R.T.J. Morris, "Load balancing in distributed systems", IEEETrans. Computers, Vol. C-43, no. 3, Mar 1985.
| [Wan92] Q. Wan and and K. Cheng, "A heuristic of scheduling parallel tasks and itsanalyssis", SIAM J. Còmput, Vol. 21, no. 2, pp. 281-294, 1992.
I [WirSO] N. Wirth, "Algoritmos + estructuras de datos = programas", Ediciones delCastillo, Madrid, 1980.
I
I
I
160
Referencias
II •
[Wu88] M. Y. Wu and D. Gajski, "A programming aid for hypercube architectures",• J. Supercomputing, Vol. 2, pp. 349-372, 1988.
[Wu94] S. S. Wu and D. Sweeting, "Heuristic algorithms for task assignment andI scheduling in a processor network", Parallel Computing, Vol. 20, pp. 1-14," 1994.
I [Yan91] T. Yang and A. Gerasoulis, "A fast static scheduling algorithm for DAGs onan unbounded number of processors", Proc. of Supercomputing'91, IEEE, pp.
m 633-642, 1991.
[Yan92] T. Yang and A. Gerasoulis, "PYRROS: Static task scheduling and codegeneration for message pasing multiprocessors", Proc. &th ACM Int'l Conf.Supercomputing (ICS92), ACM Press, New York, N. Y., pp. 428-437, 1992.I
|[Yan94] T. Yang and A. Gerasoulis, "DSC: scheduling parallel tasks on an unbounded
number of processors", IEEE Trans. Parallel and Distrib. Còmput., Vol. 5,no. 9, pp. 951-967,1994.
™ [Zim90] H. Zima and B. Chapman, "Supercompilers for parallel and vectorcomputers", ACM, New York, 1990.
I
I
I
I}
I*
I
I
I
I
I
I
161
Apéndice A
IIII• Apéndice A
IGrafos DAGs
I En este apéndice se incluye una representación de los distintos DAGs que se utilizaron para* generar TIGs irregulares y para simular su ejecución. De cada uno de los grafos se muestra una
reproducción a escala de la estructura que presenta el DAG de tamaño real.
I
I
I
I
I
I
I
I
I
I
I
I
A-l
IIIIIIIIIIIIIIIIIIIII
Apéndice A
Grafo Gl: Algoritmo de Bellman-Ford para la búsqueda de los caminos de menor longitud entre unlos nodos de un grafo dirigido y un nodo destino
G2. Algoritmo sistólico de multiplicación de matrices
A-2
IIIIIIIIIIIIIIIIIIIII
Apéndice A
G3. Algoritmo sistólico para el cálculo de la transitive closure de un conjunto de elementos
G4. Algoritmo genérico de una aplicación divide-and-conquer
A-3
IIIIIIIIIIIIIIIIIIIII
Apéndice A
G5. Algoritmo de eliminación de Gauss (back-substitution)
G6. Algoritmo de Warshall para determinar la transitive-closure de un grafo.
A-4
IIIIIIIIIIIIIIIIIIIII
Apéndice A
G7. Algoritmo de Strassen para realizar multiplicaciones rápidas de matrices
G8. Algoritmo de tipo master-slave concatenado al algoritmo de eliminación de Gauss
A-5
Apéndice A
G9. Algoritmo de resolución de la ecuación de Poisson usando el método de black-red relaxation.(algoritmo derivado del programa PDE1 de GÉNESIS 2.2)
G10. Árbol de búsqueda de Prolog
A-6
IIIIIIIIIIIIIIIIIIIII
Apéndice A
Gl 1. Grafo de algoritmo sistólico genérico del tipo "tiempo-espacio"
G12. Grafo de algoritmo sistólico para calcular un producto de matrices
A-7
IIIIIIIIIIIIIIIIIIIII
Apéndice B
Apéndice B
Resultados de asignación de grafos pequeños
En este apéndice se muestran los resultados obtenidos en la función de coste por parte de losalgoritmos CA CRM, CRME y el método óptimo para grafos irregulares de tamaño pequeño.También se muestran los resultados obtenidos por las estrategias anteriores junto con LPTF, LGCF,S A y TS en la asignación de grafos regulares de tamaño pequeño.
En el casos de las estrategias TS y SA la columna m indica el valor mínimo alcanzado por lafunción de coste, M indica el valor máximo y Med indica el promedio del total de cincoejecuciones.
B-l
111111111111111111111
Apéndice B
msftr**»fcí,*ñís ;•*
Tabla B-1 : Resultados Algoritmo óptimo(grafos irregulares)
Num. Proc.gr_15_l_lgr_15_l_llgr_15_l_5gr 15 1 15gr_15_2_lgr_15_2_llgr_15_2_5gr_15_2_15gr_15_3_5gr_15_3_15grJ6_l_lgr_16_l_l 1gr_J6_l_5gr_16_l_15gr_16_2_lgr_16_2_llgr_16_2_5gr_16_2_15gr_16_3_5gr_16_3_15gr_17_ljgr_17_l_l 1gr_17_l_5gr 17 1 15gr_17_2_lgr_17_2_llgrJ7_2_5gr 17 2 15grJ7_3_5gr_17_3J5gr_20_l_lgr_20_l_l 1gr_20_l_5gr_20_l_15gr_20_2_lgr_20_2_l 1gr_20_2_5gr_20_2_15gr_20_3_5gr_20_3_15
250742386898190249685275617504923464576912396393458856272
251846109952521194127646965268877134110337999431909
4364913236073841493771783623735128340737115135322851344471424488879161388268445444315045010582196531263505
830388619951629121611921536258118754529520414629833408424766581022231602613434892447160121294159291
-j'*£¿w 'íí̂ Í̂ *f5iw»§l£sfl!!í
i
B-2
111111111111111111111
Apéndice B
Tabla B-2: Resultados Algoritmo CA(grafos irregulares)
Num. Proc.grJ5J_lgr 15 1 11grJ5_l_5gr 15 1 15gr_15_2_lgr 15 2 11grJ5_2_5gr_15_2_15gr_15_3_5gr_15_3_15gr_16_l_lgr_16_l_llgr_16_l_5gr_16_l_15gr_16_2_lgr_16_2_l 1gr_16_2_5gr_16_2_15grJ6_3_5gr_16_3_15gr_17JJgr 17 1 11gr_17_l_5gr_17J_15gr_17_2_lgr_17_2_llgr_17_2_5gr 17 2 15gr 17 3 5gr_17_3_15gr_20_l_lgr_20_l_l 1gr_20_l_5gr_20_l_15gr_20_2_lgr 20 2 11gr 20 2 5gr_20_2_15gr_20_3_5gr_20_3_15
25680
265746
8190
289853326667
5658
2887507691
2687273799817380
29493411195
3028814619006973
3131039
134120406
1135465
1058
44154
179438
78101196526205441
3937
1484227779
178469284601
5751
17452010891
1975203036014845
17059511788
243655335640
8303895
2485566
124286136241
412588
2145559
112254179367
3440
102298
6962
124298183328
3635
102309
8366
144360199343
..
B-3
111111111111111111111
Apéndice B
; t
Tabla B-3: Resultados Algoritmo CRM(grafos irregulares)
Num. Proc.grJ5_l_lgr_15_l_llgr_15_l_5gr_15_l_15§r_15_2_lgr_15J2_llgr_15_2_5gr 15_2_15grJ5_3_5gr_15_3_15grJ6JJgrJ6_l_llgrJ6_l_5gr_16_l_15gr_16_2_lgr_16_2_llgr_16_2_5grJ6_2_15gr_16_3_5gr_16_3_15grJ7_l_lgr_17_l_llgrJ7_l_5gr 17 1 15gr 17 2 1gr 17 2 11gr_17_2_5gr 17 2 15gr_17_3_5gr_17_3_15gr_20_l_lgr_20_l_l 1gr_20_l_5gr_20_l_15gr 20 2 1gr_20_2_l 1gr_20_2_5gr_20_2_15gr_20_3_5gr 20 3 15
2567723871081902657282816355054240650769125765134588962792548641119525274746178369662748901341203461008446930
4414914138178851634051863713735128346777515838924453449491494878881167442268467444315947611188202547297526
8303888199516396286130218412588214555996239154331344093272685912429817726436351002117560127309177304
, j4
B-4
111111111111111111111
Apéndice B
Tabla B-4: Resultados Algoritmo CRME(grafos irregulares)
Num.Proc.grJ5J_lgr 15 1 11grJ5_l_5gr 15 1 15grJ5_2_lgr_15J2_llgr_15_2_5gr_15_2_15gr_15_3_5gr_15_3_15grJ6J_lgr_16_l_llgr_16_l_5gr_16_l_15gr 16 2 1gr_16_2_llgr_16_2_5gr_16_2_15gr_16_3_5gr_16_3_15gr_17_l_lgr_17_l_llgrJ7_l_5gr_17_l_15gr_17_2_lgr_17_2_llgr_17_2_5gr 17 2 15gr 17 3 5gr_17_3_15gr_20_l_lgr_20_l_llgr_20_l_5gr_20_l_15gr_20_2_lgr_20_2_l 1gr 20 2 5gr_20_2_15gr_20_3_5gr_20_3_15
25677
238706
8190
250728281635
5054
240650
7691
2396513458896279
25485711195
2527474127726966
274860134120346
1008446930
44149
1323817485
157394178365
3735
128346
7771
1533752305264948
149457
8879
1673952684584443
15946711188
200547278522
8303888
199516396
244119215
412581
187555396
239154310
334093
2496858
105226169264
363596
2467560
127291159272
t
* •«
B-5
111111111111111111111
Apéndice B
Tabla B-5: Resultados Algoritmo óptimo(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 11Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout- 1Inout-11Inout-5Inout- 15Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
29188
568888121112592912150150664984142130670
1030124112592912146128608928
9188
56888810296
576896160144624944
47262
296456
6158
312472150134384522
8668
366566
8472
31247210688
328488
6156
296456
6256
296456128104344504
84338
164244
6152
172252150114244324
7262
242362
7460
180260
8668
188268
4236
1562364236
156236
8668
188268
--
B-6
111111111111111111111
Apéndice B
Tabla B-6: Resultados Algorimo C A(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 1 1Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-11Inout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
29188
8481328
121118778
1218150150664984142134856
133612414060892814612860892810188
56888810296
576896160144624944
47266
4446846158
3585581501505948749384
36656610510035251210688
328488
6256
296456
6256
296456128104344504
84338
218338
6156
296456193154454654
7262
242362
8468
188268
8668
188268
4236
156236
4236
1562368668
188268
S
B-7
111111111111111111111
Apéndice B
i
Tabla B-7: Resultado Algoritmo CRM(grafos regulares)
Num. Proc.Binary- 1Binary- 1 1Binary-5Binary- 15Binomial- 1Binomial- 11Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-11Inout-5Inout-1 5Mesh-1Mesh-1 1Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring-1 1Ring-5Ring- 15Torus- 1Torus- 1 1Torus-5Torus- 15
29188
584904121112592912150150664984142132678
1038124112608928146128608928
9188
56888810296
576896160144624944
47262
2964566158
328488150150384544
8668
366566
8490
35251210688
3284886156
296456
6256
296456128104344504
84338
164244
6152
1722521531142443247262
242362
8468
188268
8668
188268
4236
156236
4236
156236
8668
188268
•
-VÍ
I
•4
B-8
111111111111111111111
Apéndice B
Tabla B-8: Resultados Algoritmo CRME(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 1 1Binomilal-5Binomial- 15Forkjoin-1Forkjoin-1 1Forkjoin-5Forkjoin-1 5Inout-1Inout-1 1Inout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
29188
584904121112592912150150664984142132670
1030124112608928146128608928
9188
56888810296
576896160144624944
47262
296456
6158
3124721501503845228668
366566
8490
32848810688
328488
6156
296456
6256
296456128104344504
84338
164244
6152
172252153114244324
7262
242362
8460
180260
8668
188268
4236
1562364236
156236
8668
188268
j
•̂ "
B-9
111111111111111111111
Apéndice B
Tabla B9: Resultados Algoritmo LPTF(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 11Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-11Inout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
2113104584904146128608928234192672992222186726
1086212176656976256208688
1008168144624944168144624944256208688
1008
49580
32048010688
32848828221645661617113843863816112836852817213637653610688
32848810688
328488194152392552
88668
188268
8668
188268306228328428129102282402
9776
19627610884
2042846452
172252
6452
17225210884
204284
B-10
111111111111111111111
Apéndice B
Tabla B-10: Resultados Algoritmo LGCF(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 1 1Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-1 1Inout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 1 1Torus-5Torus- 15
2102120600920123112592912223184664984211178718
107815613667299214617665697611396
600920124128608928212176672992
48472
328488
8374
32848817313438454412810640660611798
360520116104376536
7472
320480
8476
328488128130376536
86454
172252
8668
188268163114244324
7568
242362
8668
188268
9678
2042844252
172252
5252
17225211884
204284
A
*
B-ll
111111111111111111111
, Apéndice B
Tabla B- 1 1 : Resultados Algoritmo TS (grafos regulares)Num. Proc.
Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 1 1Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-11Inout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
2m9188
568888123128608928223184664984145130670
103018414460896014612860892814596
584904124112592912212144672976
M124104584904123128608928223184664984189162702
1062124160648968212160608928156120592904146112592912212192688992
Med.I l l98
578898123128608928223184664984163142676
1050124152640963186147608928147110588904137112592912212154675982
4m7262
312472
6172
32847217313438432212780
39059810588
33649610688
328488
6456
304464
8272
312472160130360520
M8372
312472
8372
32847217313438432212784
3986061061043445121161083605206456
312472
8472
312472172130360536
Med.7870
312472
7472
32847217313438432212783
39260310510134150610996
352496
6456
309470
8272
312472167130360530
8m4338
164244
6352
172252153114244324
7262
242362
7560
180268
8668
1882684236
156236
4236
156236
8668
204284
M4338
164252
6352
172252153114244324
7262
2423627560
180268
8668
1882684236
1562364236
156236
8668
204284
Med4338
164249
6352
172252153114244324
7262
242362
7560
180268
8668
1882684236
1562364236
156236
8668
204284
' • •«*•
i
B-12
iniiiiii^^^^^^^^^^
111111111111111111111
Apéndice B
Tabla B- 12: Resultados Algoritmo SA (grafos regulares)Num. Proc.
Binary- 1Binary- 11Binary-5Binary- 15Binomial- 1Binomial- 11Binomilal-5Binomial- 15Forkjoin-1Forkjoin-11Forkjoin-5Forkjoin-1 5Inout-1Inout-11lnout-5Inout-1 5Mesh-1Mesh- 11Mesh-5Mesh- 15Nbody-1Nbody-1 1Nbody-5Nbody-1 5Pipe-1Pipe-1 1Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15Torus- 1Torus- 11Torus-5Torus- 15
2m918856888812311259291222318466498414513067010301241125929121461286089281128856888810296576896168144624944
M918856888812311259291222318466498414513067010301241125929121461286089281128856888810296576896168144624944
Med918856888812311259291222318466498414513067010301241125929121461286089281128856888810296576896168144624944
4m72622964566158
312472173134384522866836656684723124721068832848863562964566256296456128104344504
M72622964566158
312472173134384522866836656684723124721068832848863562964566256296456128104344504
Med72622964566158312472173134384522866836656684723124721068832848863562964566256296456128104344504
8m43381642446152172252153114244324726224236274601802608668188268423615623642361562368668188268
M43381642446252172252153114244324746224236274601802608668188268423615623642361562368668188268
Med43381642446152172252153114244324736224236274601802608668188268423615623642361562368668188268
B-13
-
I•
Apéndice C
,
I
I• Apéndice C
IResultados de asignación de grafos grandes
J En este apéndice se muestran los resultados obtenidos en la función de coste por las estrategias CA,CRM, CRME, LPTF, LGCF, SA, TS, ED y EDTR al asignar grafos regulares e irregulares de
• tamaño grande.
En el caso de las estrategias TS y SA la columna m indica el valor mínimo alcanzado por la función• de coste, M indica el valor máximo y Med indica el promedio del total de cinco ejecuciones.
I
I
I , .t
I ' -
I
I
I
I
I
I
I
C-l
111111111111111111111
Apéndice C
Tabla C-l: Resultado Algoritmo LPTF(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Torus- 1Torus- 1 1Torus-5Torus-15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
81156928
28484128180014404320624025902020502070202656206850687068253619784972697215781284428462841578128442846284
16600480
14402080944752
21923152131710262526352613501050255035501350105025503550
800650
21503150
800650
21503150
32300240720
1040494392
11121592702546
13261846702546
13261846702546
13261846416336
11181638416338
11181638
Tabla C-2: Resultados Algoritmo LPTF(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
814943088304281241224
14497218484
22441813304
16796
165416165852
70013268811665
1176247516
'32474976836
4792462
1256538800
624844320
C-2
111111111111111111111
Apéndice C
Tabla C-3: Resultados Algoritmo LGCF(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Toras- 1Toras- 11Toras-5Toras- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8715624
2656393613671146418261201872159047706804203016244860687419041546485268681096980
416461961088101241786236
16359352
13602000
725622
214231201084850
245434381130906
25023518954872
24863486
612526
21103142
600548
21503150
32215210688
1008395330
10881568569458
12541774604472
12941814514460
12941814318296
11021622326296
10861606
Tabla C-4: Resultados Algoritmo LGCF(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
813392772265252901154
12507813058
19496011534
16756
149214464792602
1250786979
1048226222
: 32406836788
4792462
1250786401
536523196
C-3
111111111111111111111
Apéndice C
Tabla C-5: Resultados Algoritmo TS (grafos regulares)Num. Proc.
Binary- 1Binary- 11Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Torus-1Torus- 11Torus-5Torus- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
Num. Proc.
GlG2G3G4G5G6G7G8G9
8m473448260838727877364072592010291008463466441024924465867001122101647066652910912
411461641008916
41246124
M529458265639268149884128603215641174473067301526128847806812140414704796671610741038416461941070100841726220
Med4794522646392079582240866016120711064652668613241118475067641242128047266694103295041506188102895241566186
Tabla C-6:8
m10772066181647921140
1250789116
1646968974
M11082466197047921144
1250789776
1728789676
16m230242134419843743862088304848247623983422768558243834705184582486347045742221023118470394
21183150
M24724413602000426386213430565315062422343888679424543510564504248634904604222150311848244621503158
Med24024413521992398386201230525154942406342882666424423480553473248634764584222132311847642221303152
32m123122672992205186105615362922441222174231625812461782210178123017761741681054158219617810541574
M125130672992208200107215442962741246177434026812621782232188126217821941841070160620820410701590
Med124128672992206194106415392952501238175832126212521782216182124317781821781060159019818410601580
Resultados Algoritmo TS (grafos irregulares)
Med.10902174189947921142
1250789506
1687129412
16m M659 6681098 13781078 11784792 4792602 602
125078 1250785377 537785544 890665146 5554
C-4
Med664118110964792602
1250785377876045321
32m M Med406 406 406664 722 694620 642 6344792 4792 4792462 462 462
125078 125078 1250785377 5377 537746650 47924 471642844 2972 2898
111111111111111111111
Apéndice C
Tabla C-7: Resultados Algoritmo SA (grafos regulares)Num. Proc.
Binary- 1Binary- 1 1Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Toras- 1Toras- 1 1Torus-5Toras- 1 5Nbody-1Nbody-1 1Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8m36637023503680607568350254087366763772577884075038265866602586
371457545565583660577256856436925852
M4353822366369661061235425448740704
3816587484276638965960638596
381058165685603706578858858437725868
Med38337423633692608594353654327376873799581384075638765898616594376258025665583670577657857437525856
16m24221012641920368336183827524604161966299051244220223086362336198629563163082006302230630820223054
M2432281280193638534218382808476450
2012303652246820863310372338198629563283242022302831833420383054
Med2422141275193037834018382772466429199730215164622054316636933619862956322314
2017302331432420283054
32m161128672992227.200944140831828010381558336294120817182162161076160817417810701574182188
10701590
M1971306729922282029441424336292105415743883301230175025622610861622198194
10701590186194
10861606
Med1681396729922272029441416322284104415643683141224173423222010801614186188
10701584185190
10801594
-
Tabla C-8: Resultados Algoritmo SA (grafos irregulares)Num. Proc. 8
mGl 1098G2 1828G3 1696G4 4792G5 1134G6 125078G7 8232G8 146696G9 5690
M Med. 1116 1104
1864 . 18471764 17424792 47921134 1134
125078 1250789700 .. 8889
149592 1481925906 5803
16m652117410324792598
1250786146794883492
M Med652 6521260 12161128 10804792 4792598 598
125078 1250786813 638185216 814813594 3539
32m M Med406 406 406738 772 758644 714 6894792 4792 4792462 -462 462
125078 125078 1250785377 5377 537745656 47080 461812182 2380 2288
C-5
IIIIIIIIIIIIIIIIIIIII
Apéndice C
Tabla C-9: Resultados Algoritmo CA(grafos regulares)
Num. Proc.Binary- 1Binary- 1 1Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Toras- 1Toras- 1 1Toras-5Toras- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring-1 1Ring-5Ring- 15
8415496
33765298816852
381459341036948
48327392992896
47367296706688
45287088662656
44967056662656
44967056
16276240
14402240420444
22743514628544
24643744584512
24323712
386368
22883568
342336
22563536
342336
22563536
32161158958
1478242236
13322052
376320
12801920336288
12481888226208
11681808
182176
11361776
182176
11361776
Tabla C-10: Resultados Algoritmo CA(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
813112352236252961540182654105751969768216
1684313761296479281015117455861071844992
3247073677647924621252695377577122930
C-6
111111111111111111111
Apéndice C
Tabla C-l 1 : Resultado Algoritmo CRM(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Inout-1Inout-1 1Inout-5Inout-15Mesh-1Mesh-1 1Mesh-5Mesh-1 5Torus- 1Torus-11Torus-5Torus- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe-1 1Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8363354
22883568
764598
34245344
829736
38105844
840750
38105850615576
3618. 5644
542528
35945626542532
35645564
16262192
11521792305288
17682728
502436
19803012
524452
2012„ 3052
355328
18682908292286
18362846292286
18362846
32161114632952242188944
1424305266
10541574326278
10481558216198
10161478
172158926
1446172162926
1446
Tabla C-12: Resultados Algoritmo CRM(grafos irregulares)
Num. Proc. 8Gl 1199G2 2224G3 1836G4 4792G5 1214G6 125078G7 7982G8 158468G9 6648
16 32728 466
1090 6661058 7144792 4792
778 462125078 125078
5377 537786780 466803848 2348
C-7
111111111111111111111
Apéndice C
Tabla C- 13: Resultados Algoritmo CRME(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Inout-1Inout-11Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Torus-1Torus- 1 1Torus-5Torus- 1 5Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8363354
22723552
764598
34005320
829736
37945794
840750
38105850615576
36185644542528
35945626542532
35645564
16262192
11521778305288
17442704
502436
19802996
524452
20123052
355328
18682908292286
18362830292286
18362830
32161114624944242188928
1408305260
10541574326278
10381558216198968
1478172158926
1446172162926
1446
Tabla C-14: Resultados Algoritmo CRME(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
811991892183047921150
1250787891
1584686346
16 32680 406
1090 6641058 6344792 4792
618 462125078 125078
5377 537784102 456563794 2262
C-8
111111111111111111111
Apéndice C
Tabla C- 15: Resultado Algoritmo ED(grafos regulares)
Num. Proc.Binary- 1Binary- 1 1Binary-5Binary- 15Inout-1Inout-1 1Inout-5Inout-15Mesh-1Mesh-11Mesh-5Mesh-1 5Torus-1Toras- 11Toras-5Toras- 15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8630550
24803776
874788
370656281094880
403860641104962
40126046155913364528657412801092421462921280109242146300
16336288
12481888493436
19122904
737540
21743174798656
21823198936758
23583358
725598
21503150736598
21503150
32168144624944276240
10001486428336
11501670472376
11501670538424
12301750384312
11181638384312
11181638
Tabla C-16: Resultados Algoritmo ED(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
813262414211847921288
1250788445
1697307430
16 32807 442
1342 8441176 6784792 4792
718 462125078 125078
5377 537798010 59140
4554 2864
C-9
111111111111111111111
Apéndice C
Tabla C-17: Resultado Algoritmo EDTR(grafos regulares)
Num. Proc.Binary- 1Binary- 11Binary-5Binary- 15Inout- 1Inout-11Inout-5Inout- 15Mesh-1Mesh-11Mesh-5Mesh-1 5Torus- 1Torus- 1 1Torus-5Torus-15Nbody-1Nbody-11Nbody-5Nbody-1 5Pipe-1Pipe- 11Pipe-5Pipe- 15Ring-1Ring- 11Ring-5Ring- 15
8596468
24563686711674
361055321079840
394859361064938
39826088144612684458642811121086414660821242108641466082
16303262
12241864431396
18802803704514
21103110746610
21663166
826728
22883238622576
21163096702566
21163096
32167144624944284218958
1470416312
11021654446344
11341654436338
11021698252306
10061556312306
10661556
-
Tabla C- 1 8: Resultados Algoritmo EDTR(grafos irregulares)
Num. Proc.GlG2G3G4G5G6G7G8G9
811612234193647921144
1250788136
1541826822
16 32693 406
1290 7941092 6464792 4792
598 462125078 125078
5377 537785852 482044084 2520
C-10
IiIIIIIIIIIIIIIIIIIII
Apéndice D
Apéndice D
Resultados de asignación con arquitectura
En este apéndice se muestran los resultados obtenidos por las diferentes estaregias deasignación que consideraban la existencia de arquitectura. Se muestran también los valorescorrespondientes a la estrategia CRME que era la base de la comparación de los resultados.Las tablas contienen los valores de la función de coste minimax (Minim.) y del volumen decomunicaciones (Comunic).
D-l
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D. 1 Valores de función minimax y volumen de comunicación global (estrategia CRME)Num Proc.Grafobina400_lbina400_l 1bina4QO_15bina400_5inout400_linout400_l 1inout400_15inout400 5torus400_ltorus400 11torus400_15torus400_5mesh400_lmesh400 11mesh400 15mesh400_5ring400_lring400_l 1ring400_15ring400_5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_llnbody399_15nbody399 5glg2g3g4g5g6g7g8g9
8Minim.
363354
35522272
764598
53203400
840750
58503810
829736
57943794
542532
55643564
542528
56263594
615576
56443618119947921150
1250787891
158468634615361784
Comm.88
120104104198448232192
1331968
113610881276912
11041064
132104128128143104320280396280352352
244075081900
1204877016
16761611048
9001768
9Minim.
321336
32142054
764522
47703062
780690
51903390731676
52123374492482
49663166492486
49823228
595558
49983268104147921024
1250787105
138294577615361784
Comm.110208264248198416360360
14361088119211601232100812161120
187144232216198160256312594440432632
268865321932
1204877500
15484811788
11562020
16Minim.
262192
17781152305288
27041744524452
30522012
502436
29961980292286
28301834292286
28301836355328
29081868680
4792618
1250785377
841023794
8961144
Comm.176192184200374328464464
21231560187218721870139216241568297224320336277248360352748544
1056896
321669362032
12048710312
2005801557619243784
32Minim.
161114944624242188
1408928326278
15581038305260
15741054
172162
1446926172158
1446926216198
1478968406
4792462
1250785377
456562262
576824
Comm.341368640632671952920920
30252224256824642618200823282296
638464632632638456624624
1353992
14641384377689762112
12048714308
22944821200
39727816
D-2
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-2: Resultados del algoritmo EMB (Mallas)Num. Proc.Grafobina400 1bina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400 15torus400_5mesh400 1mesh400 11mesh400 15mesh400_5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399Jnbody399_l 1nbody399_15nbody399 5glg2g3g4§5g6g7g8g9
Malla 9Minimax
332350
32302070
514498
49763200
924798
53263518900770
53123516786564
48103118
519502
49823236634592
5024335413091886189467601268
1422359160
1539226832
Commun.143240320304253184288288
19141416163215681573127214801424231528488472242200296352726544496816
34202888319297162888
14265210440
19091214584
Malla 16Minimax
277232
19141184339330
28701862852652
32702280741640
32482210
327328
27361776330310
28861902390424
3032200810631574146477401080
1777048449
1127206084
Commun.209328352360484368512560
349824963440353628602160.27762512462480704704440384568600957792
17201504526054204852
115244292
17812216128
33193223456
Malla 32Minimax
188194
1072728243222
15041024766542
19681376683508
19281416325296
15521072227198
14961024370278
16581218989
11721228
12032782
2214037425
899565620
Commun.462632
128812001144848
131213126094459262245696520337685200465611221760168016801100824
128012801925136033042888895283448444
201406516
22182124008
46191642880
D-3
1Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-3: Resultados algoritmo EMB (Hipercubos)
bina400 1bina400 11bina400 15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400 5mesh400 1mesh400 11mesh400_15mesh400 5inout400 1inout400_l 1inout400_15inout400_5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Cubo 8Minim ax
363358
35602280
553544
559635961173984
603439721065936
59183950786696
53303424567544
56343602650618
5716366614942176217475761530
15286510697
1907568156
Commun.88
136112112154128192192
20901520171216481859123214641440242680272256209144392336451400528528
360032683136
123083248
15302610028
23631614844
Cubo 16Minimax
299216
19141178336318
28701876759620
33162280
741600
32482210
317320
27281786330316
28861910390424
3056200810631574146477401080
1777047937
1127206084
Commun.264312384344462352544592
35202592355234882860203227762512440496656656506376568616957792
17841552526054204852
115244292
17812216132
33193223456
Cubo 32Minimax
199218
1024688-243230
14881008606510
18161312551470
17901288314272
15041024243212
15121032304246
16261130845984994
10524658
1970666913
748164270
Commun.451656
113610961100856
1176117654894120500848804422352043924344
9681560150415041067864
128012801925135228082440750474407112
178765444
19748420720
40139636308
D-4
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-4: Resultados algoritmo EMB (Anillos)Num. Proc.
Grafobina400 1bina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400 15torus400 5mesh400 1mesh400 11mesh400 15mesh400_5inout400_linout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Anillo 8Minimax
374376
35762296
589568
5628362812171016616441641189112860384038
819752
53623432602568
56663618
760710
5788371816942516259098321810 ,
19659013037
2026289788
Commun.99
168144144264192256256
23101680232022242288172917761624297808328288253216464400627624720720
442840043976
161924328
19251415684
30278020368
Anillo 16Minimax
409288
21701290449402
2982197415071292387028721467928
38642666426400
28401898418398
30302030
649582
33122362157627582172
140601992
29346816129
16008411632
Commun.429536720664
1012736
1024112064464832704070245071320052485120
781896
13201320913808
122411362475181630723056765292568352
219368564
29414131484
61706843096
Anillo 32Minimax
337434
14981026441526
1784130418011388288022241596129229282418
525626
18961416463462
18321352744716
24501906277029962662
329202062
45799214593
21390413106
Commun.858
1648340833443190291238723872
16874128161760014912130799328
1297612016251940163624362432452856376837686358511294488816
2322821616213525090417412
45815567076
995168104600
D-5
1B Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-5: Resultados algoritmo BOK_1 (Mallas)Num. Proc.
Grafobina400 1bina400 11bina400 15bina400 5r¡ng400_lring400_l 1ring400_15ring400_5torus400 1torus400 11torus400 15torus400_5mesh400 1mesh400 11mesh400_15mesh400_5inout400_linout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399_5
glg2g3g4g5g6g7g8g9
Malla 9Minimax
332350
32302070
503490
49763192
901766
52963488
845770
53303474786564
48103118519494
49823236623592
50243354122218621858
.69561268
1422359400
1539226832
Commun.132240312296220160288272
18481288155214801485127214641352231520480464231184296352704528496816
33202776295688882888
13790110012
19091214584
Malla 16Minimax
277216
19141184330298
28701862737604
32642288
741588
32242210
317328
27361776319308
28781878388368
3064201810241422133277401080
1777049217
1110406084
Commun.198272320280396288496544
33882464324831842827204826162512440480656656385336560520935744
16401424512849204508
113564292
17812214484
31811623456
Malla 32Minimax
188168
1040728221198
14961016672508
19521296573492
19441392314266
15201040243190
14961016364278
165011701009940
102611920
750221534
9473748844662
Commun.451560
11521152968736
126412645874446458245072471935924920443210671688160816081012712
122412241815132829682456772870687928
185046500
22169722692
43842838884
D-6
1— Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-6: Resultados algoritmo BOK ! (Hipercubos)Num. Pròc.
Grafobina400 1bina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400_15torus400_5mesh400 1mesh400 11mesh400 15mesh400 5inout400 1inout400_l 1inout400 15inout400_5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
gl§2g3g4g5g6g7g8g9
Cubo 8Minimax
363358
35602280
553544
558835881040890
602039481068872
59183950786682
53303408
564544
56343602628634
5716364615262204217476401530
15286510697
1907568156
Commun.88
136112112154128176176
18701360166415681738120014641440242624272224187144384328429368480480
346432603136
113323248
15302610028
23631614844
Cubo 16Minimax
299216
19141176330294
28781868747636
32642288741568
32242210
317312
27281768306316
28861862388360
3072201010241468129280801080
1777048449
1110406084
Commun.231280320280418256496560
33222448324833122827192026002512440480656656352360568528935704
16081472512848524468
113964292
17812214112
31811623456
Cubo 32Minimax
177138
1024688210190
14801000562484
17761248518420
17601288292278
15201040221196
14801000304246
15921106825
1012888
10488658
1970666913
711324134
Commun.429504
10641056858728
1112111250933792483245444345336842004000
946152813841384913712
107210721892135224562160712471526596
158285432
19748419812
37872435356
D-7
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-7: Resultados Algoritmo BOK:_1 (Anillos)Num. Proc.
Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400 1torus400_l 1torus400_15torus400 5mesh400 1mesh400 11mesh400 15mesh400 5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Anillo 8Minimax
374362
35762296
579560
5620362012171016614841641170100860384038
786746
53623440
591568
56503618760648
5788371817182516247099761810
19659013889
2157509468
Commun.99
136144144220144240240
23101680219220962134154417761624275752328280242184432392627448656656
432040043856
148124328
19251413912
29624419544
Anillo 16Minimax
376248
21701282352334
298220161298908
384028961280928
38962698405384
28481888352380
30061976418398
32642338143521101960
140401992
29346817153
15465611708
Commun.352440576480506400864
102458084064632063684807315250964528
748816
11041104539544
111210241023752
29922656733682447292
217088564
29363125076
55582842264
Anillo 32Minimax
381330
1410968309268
1808132813981092282421281420130028162250
534602
18561376287268
18321352320316
24501858207320681914
317682062
45799225601
1715969418
Commun.781
1136281626401298123230403040
14894112641404812976111327976
1213610688237638723400340012981192295229522068152063525528
1586016488156604916817412
45815553292
90749675356
D-8
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-8: Resultados Algoritmo BOK_2Num. Proc.Grafobina400_lbina400 11bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400 15torus400_5mesh400_lmesh400 11mesh400_15mesh400_5inout400_linout400 11inout400 15inout400_5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Malla 9Minimax
332350
32222064
503490
49743192
901766
52723470
819770
52823474764564
48103118
510494
49823228619590
5024333612121852185867601268
1422359160
1523306720
Commun.132240344288220160288272
18481288151215201430127214961352209520480464253176296368737544496808
33762832295692682888
137901. 10280197108
14832
Malla 16Minimax
273208
19141176314294
28701854737620
32202248
708592
31842122
317312
27361776314302
28701854388368
3016197810081396130477401080
1777047937
1070165742
Commun.209248320304418288496544
33882528339234882849219228562472440480656656407336560528935744
16081488531251084640
113564292
17812214032
33744425960
Malla 32Minimax
177146
1024688210198
14861008595492
18241312529444
18001272261262
1472992210188
1478992293270
16401106833940964
11156750
2214037425
680604290
Commun.473576
12881168990800
126412806006491259045680489538325232478410671736164816481034728
12081216188113683208272888767932'8708
215526500
22182123608
44562042880
D-9
1— Apéndice D
1
1
i11111111111111111
Tabla D-9: Resultados algoritmo BOK_2 (Hipercubos)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400 5mesh400 1mesh400 11mesh400 15mesh400 5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
glg2g3g4g5g6g7g8g9
Cubo 8Minim ax
363358
35602280
553544
558835881040890
598039721065872
59183938786682
53303408558544
56343602628616
5716364614822176217474721510
15286510697
1844568110
Commun.88
136112112154128176176
18701360169616481859120014641480242624272224187144384328429416480480
351232683136
114643248
15302610028
24287616592
Cubo 16Minimax
273216
19141176319302
28621854759620
32282240664568
31762138
317312
27281768314308
28701854388374
30241986991
1368128877401080
1777047937
1075965658
Commun.209280320280418304512560
35202544339234562750192027922536440480656656429360568520935752
16561488521650684496
113564292
17812214728
33941226692
Cubo 32Minimax
177136
1016664210190
1470984551414
17601248453396
17281208259248
1456984199188
1470992271246
15781080722880834
9468646
1970666913
662163680
Commun.451488
10881080935776
11281096565439685040497644883504429642721023158414481416924760
108010801815135227442280784873967104
181045440
19748419812
42153637852
D-10
1H Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D- 10: Resultados Algortimo BOK_2 (Anillos)Num. Proc.Grafobina400 1bina400_l 1bina400_15bina400 5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400 15torus400 5mesh400_lmesh400_l 1mesh400 15mesh400 5inout400 1inout400_l 1inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_llnbody399_15nbody399 5glg2g3§4g5g6g7g8g9
Anillo 8Minimax
374362
35762296
567560
561236121161978
613241001189974
60384038
786746
53623424580560
56503610662648
5788371816942404245097281810
19659013037
2006289252
Commun.99
136144144220144240240
23541712224021762288156017761624319872328288253184432392517464608608
442841884464
157484328
19251414772
30278019568
Anillo 16Minimax
310248
21701250352318
295819501265932
380827921116860
37042552393376
28241856352366
29741990418472
32642242140720961972
136361992
29346813569
1508809260
Commun.352440576472528400
1008108866884768723273125830352058325536
814832
11921184539696
112010961023126430402928742887768628
223928564
29663131232
63328851408
Anillo 32Minimax
287234
1266888243350
1712123213431020265620641255948
25121976426484
17921312243252
17281248409270
21601650196518241796
269602062
45799211777
1512889514
Commun.10121480325629281342198434403440
159281179217392
1966123208912
1339213264267341203504350412981192320832082640164085207328
2121219884193965112017412458155
712321127876
93464
D-ll
I
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-1 1: Resultados Algoritmo ITER_1 (Mallas)Num. Proc.Grafobina400 1bina400_l 1bina400_15bina400_5ring400Jring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400 15torus400 5mesh400_lmesh400 11mesh400 15mesh400_5inout400_linout400 11inout400 15inout400_5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399_5glg2g3g4g5g6g7g»g9
Malla 9Minimax
332342
32222062
503486
49763184
876748
52703462792738
52443438724548
48103112
509488
49823236601582
4998330011511784181269561248
1422358449
1473366282
Commun.132232312272220160296272
18261312156814801485127214561352253504480464231176296352671528496760
32202780300088882888
13790110140
19249213864
Malla 16Minimax
262210
18941168307296
28621846712588
31802156
634536
31762090
316312
27361776314302
28701852388352
29641976942
137212307740
906177704
9217101572
4748
Commun.220224312272396288512528
34982480312031042860208026162456418472656656385336560552935744
15281392486847964364
113564364
17812214484
32185223168
Malla 32Minimax
166146
1014702210188
1486992561454
18281280508410
17821260250252
14781006206188
1486992249248
16001076802888956
11920750
2215349473
635443734
Commun.440560
11921192946736
12641232616044965792510448843584487245281221167215681576946712
1208120817271352 .27922360779270047880
185046500
22169722692
44148438496
D-12
1•
Apéndice D
1•i-
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1I
1
Tabla D- 12: Resultados Algoritmo ITER_1 (Hipercubos)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400_15torus400_5mesh400 1mesh400 11mesh400_15mesh400 5inout400 1inout400 11inout400_15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Cubo 8Minimax
363356
35522272
545534
55803580987856
59463916907828
58743880
744632
53283408554544
56343602611592
5658364213432084204076401502
1528659059
1706327128
Commun.88
128128128154128176176
19141360163215681573123213761440352568272224187144384328429336496480
332431083072
113323248
15302610784
21411214224
Cubo 16Minimax
262216
18941176308294
28621852722606
32042164
638542
31302090
316312
27281786303302
28701862388360
30001944952
146812528080906
1777048449
1015724772
Commun.286280312280396256496592
33442448321631042904193625682456
418480656656352344568528935704
15761376519648524452
113964364
17812214112
32182523520
Cubo 32Minimax
166132
1014672193182
1478984492386
17521240507388
17181184250232
1448982205190
1470992292246
15601066722912842
10488646
1970666913
578163248
Commun.462512
10561048836728
10961096507136484816456043893528422439361034146413281376913696
105611041914135224562104714871566596
158285440
19748419812
38126035200
D-13
1— Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-13: Resultados Algoritmo ITER_2 (Anillos)Num. Proc.Grafobina400_lbina400 11bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400 5mesh400_lmesh400 11mesh400 15mesh400 5inout400_linout400_l 1inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
glg2§3g4g5g6g7g8g9
Anillo 8Minim ax
374360
35602282
565540
560435941115952
60604042
999934
59123898
786666
53363416
565568
56423610685638
5724369015452370217099761790
19659010753
1852328358
Commun.99
144160160220144240240
23541744216020801936160815361560275720280264242184432400627448736656
404841243644
148124328
19251415996
27107619164
Anillo 16Minimax
279248
19021214352312
293219081112
• 80636422562
926780
34182340
393344
28161862352340
29661900398362
32082178127220361688
140401590
29346817153
1262047258
Commun.385440592504506400864
100862264144625661445027317648324048
704704
11281088539496
1112992
1001744
28802608735683727228
217088728
29363125076
50180443304
Anillo 32Minimax
265234
1166830243268
163211801196972
248017981089832
21521728438502
17261246243244
16401232273252
19321424156617921724
317682062
45799225601927006736
Commun.792
1176288029041276123228803168
14278111521406412752120238416
1163210512236539923432341612761112274429522024152060325656
1578816772153204916817412
45815553292
84887279772
D-14
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
i111
Tabla D-14: Resultados Algoritmo ITER_2 (Mallas)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400_5mesh400 1mesh400_l 1mesh400 15mesh400 5inout400 1inout400_l 1inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_llnbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Malla 9Minimax
332342
32142062
503486
49743184
876748
52543470760738
52543444764548
48103112
508488
49823228618582
4998329211641804181267601248
1422358321
1500386428
Commun.132232344288220160288272
18261312149615201353127215041352209504480456242176296368737544496696
32002828300092682888
13790110792
19823614676
Malla 16Minimax
273208
18941176314294
28621852712604
31882224
686558
31842106
316312
27361776314302
28701854388352
301619441000133412627740
906177704
7937102720
5394
Commun.209248312304418288512528
34982528332834722926217628562472418480656656407336560528935744
16081408526848804680
113564364
17812214032
33322426376
Malla 32Minimax
177146
1024688210198
14861000595492
18161312529434
18001272261254
1472992210188
1478992293270
16401094814940952
11156750
2214037425
634924078
Commun.473576
12001168990800
126412486006491260005680489537845232478410671704164816481034728
120812161881136832082712889279328804
215526500
22182123608
43630443856
D-15
1B Apéndice D
1
1
1
1
1
1
1
1
1
•
1
1
1
1
1
1
1
1I
1
-
Tabla D- 15: Resultados Algoritmo ITERJ2 (Hipercubos)Num. Proc.Grafobina400 1bina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400_5mesh400_lmesh400_l 1mesh400_15mesh400_5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
gl§2g3g4g5g6g7g8g9
CuboSMinim ax
363356
35522272
545534
55803580987856
597039381014828
58743904744632
53283408556544
56343602
611608
5658364213972140204074721492
1528659059
1733307708
Commun.88
128128128154128176176
19141360168016321925123213761512352568272224187144384328429416496480
318432323072
114643248
15302610784
22614015968
Cubo 16Minimax
273216
18941176319296
28621854734614
32282188628542
31762106
316312
27281768314308
28701854388358
29841936932
136812347740906
1777047937
1038525296
Commun.209280328280418304512560
37182560339233602761193627922488
418480656656429360568520935752
16561360508450684452
113564364
17812214728
34380426992
Cubo 32Minimax
166130
1016664199188
1470976551414
17261248452396
17281192250246
1448976199182
1470992271246
15681064722880834
9468646
1970666913
612963588
Commun.484472
10881080891760
11281096565439684928497644443504429643121100156814081424924760
108010801815135226962232784873967104
181045440
19748419812
41568837612
D-16
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-16: Resultados Algoritmo ITER_2 (Anillos)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400 15torus400 5mesh400_lmesh400 11mesh400 15mesh400 5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400 15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Anillo 8Minimax
374360
35602282
567546
560435941129960
606640581127926
59123898
786696
53363424575560
56423610639638
5706368815062300240497281790
19659010696
1894568000
Commun.99
144160160220144256240
23761728211221442310157615361560319832280288253184432400517464576640
408839404448
157484328
19251417120
29101217064
Anillo 16Minimax
284248
19021216341318
295819261166894
364426881013802
36002506
393376
28241848352366
29741912398428
32162208140720441832
136361590
29346813569
1424488956
Commun.495440592480528400
1008104070854800700870085709350456005656
814832
11921192539696
11201016
1001126429763008742885808796
223928728
29363131232
64814853328
Anillo 32Minimax
287234
1264888243348
17121232134310202656
146401168930
23841872404446
17921312243252
17281248369262
21601500189818041778
269602062
45799211777
1091687032
Commun.10121480323029281342200034403440
15928117921739214208128268880
1323213048280540403504350412981192320832082508164085207728
2074819908194285112017412
45815571232
112314093392
D-17
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D- 17: Resultados Algoritmo MOVIM (Mallas)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400_5mesh400 1mesh400 11mesh400_15mesh400_5inout400 1inout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399J 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Malla 9Minimax
332342
32302070
503486
50083244
876748
52783462792760
52683462724550
48103110
509488
49823236
601582
5112332411721810180069561324
1422358321
1514206674
Commun.132232312312220160320384
18261312156814481485132014721416253536480472231176296352671528744816
31362824291688882896
13790111520
21214015216
Malla 16Minimax
262210
18161176 j307296
28941854712588
31882192
634536
32162098316320
28001806314302
28841854388352
3012200210261372124077401050
1777049217
1000725052
Commun.220224272272396288544544
34982480310431682860208027042448418496680680385336520536935744
16561632514047964404
113564304
17812214484
30863623036
Malla 32Minimax
166146
1016696210188
14861000561460
18281324508418
17821260250250
15181008206188
1486992249248
16881208738940998
11920750
2215349473
647683432
Commun.440560
11441184946736
12641248616044645792563248843736487245281221168016721688946712
120812081727135230003000700472006224
185046500
22169722692
41211238208
D-18
1B Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D- 18: Resultados Algoritmo MO VIM (Hipercubos)Num. Proc.Grafobina400_lbina400_l 1bina400 15bina400_5rmg400_lring400_l 1ring400_15ring400_5torus400 1torus400 11torus400_15torus400_5mesh400_lmesh400_l 1mesh400 15mesh400_5inout400 1inout400 11inout400_15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Cubo 8Minimax
363356
35762296
545534
55883588987856
59703924
921828
59183928
744640
53763456554544
56343602
611592
5666364613432110202076401550
1528659293
1786387286
Commun.88
128144144154128176176
1914136016641584161712321544
. 15283525762802801871,44384328429336480480
332431163016
113323248
15302611660
23946814652
Cubo 16Minimax
262216
18161176308294
28841860722606
31902216638542
31922098
316312
27761806303302
29001862388360
30081994956
1468125280801042
1777048449
1000725052
Commun.286280280280396256560576
33442448321632802904193627122448418472688672352344544528935704
15921600498048524452
113964304
17812214112
30406823036
Cubo 32Minimax
166132
1014686193182
1478984492386
17681272507414
17181204250236
14801000205190
1472992292246
16201120754964918
10488658
1970666913
613643348
Commun.462512968
1008836728
10961096507136484832479243893264422440161034144815041488913696
107211041914135226082672694474685640
158285432
19748419812
38270836092
D-19
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D- 19: Resultados Algoritmo MO VIM (Anillos)Num. Proc.Grafobina400_lbina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400 15torus400 5mesh400_lmesh400 11mesh400 15mesh400 5inout400 1inout400 11inout400_15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g5g4g5g6g7g8g9
Anillo 8Minimax
374360
35922312
565540
562035941126954
609040741092934
59623952786666
53763456
565568
56503618
685638
5740369015452370218899761810
19659011227
1929388078
Commun.99
144176176220144240240
23761744214421442145160816881680275720312312242184432392627448704656
404841243552
148124328
19251416384
29094018128
Anillo 16Minimax
279248
18481208352312
294819181112806
36202562
977796
35382476393362
28301834352340
29561908398362
32642234154220361758
140401700
29346817153
1339686686
Commun.385440440440506400
1088105662264144648061445225324054884400
704800
10641000539496
116810081001744
29923112760483727228
217088452
29363125076
50959235356
Anillo 32Minimax
265234
1230854243268
1736118012781004254419481089107622561728438542
16861248243244
17121232273252
19641584173816661686
317682062
45799225601
1040487210
Commun.792
1176300828481276123230243168
15004112961432014016120238536
1184010512236540323792376012761112295229522024152069287144
1412417436119644916817412
45815553292
95962881708
D-20
j
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-20: Resultados Algoritmo CA_ME (Mallas)Num. Proc.Grafobina400 1bina400_llbina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400_l 1torus400_15torus400_5mesh400 1mesh400_l 1mesh400_15mesh400 5inout400_linout400 11inout400_15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
glg2g3g4g5g6g7g»g9
Malla 9Minimax
353496
52963376662656
705644961014902
69204426
865856
64244178
724730
53123392662656
70564496
706688
7088452811511808175266521254
1381388448
1499646988
Commun.11064646499727272
16831240132814321573119213441360253200240232
88646464
330216216216
32202756276487122888
13354610284
20623215692
Malla 16Minimax
273220
20201300342336
35362256
716646
37922504
598590
35882442
390388
29321892342336
35362256
386368
35682288
899135212667740
948170407
844999444
5146
Commun.231184192192176128128128
27721904204820322354185620961936473400536552165120120120517376376376
506846004164
113564316
17082312768
30054622156
Malla 32Minimax
166162
1352872182176
17761136546438
20161376420400
20001360250252
18881248
182176
17761136250208
18081168778920896
11920750
2208909473
661763868
Commun.440400400400374288288288
4312313633123280333329922864289612211056960960341248248248
1221848824824
712477086580
185046500
22105322692
45444834672
D-21
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-21: Resultados Algoritmo CA_ME (Hipercubos)Num. Proc.Grafobina400 1bina400_l 1bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400 1torus400 11torus400_15torus400_5mesh400 1mesh400 11mesh400_15mesh400 5inout400_linout400 11inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5
glg2g3g4g5g6g7g8§9
Cubo 8Minim ax
375496
52963376662656
705644961080940
70004512
921922
67404030
764814
53843464
662656
70564496
706688
7088452813472236217870961550
177149330
1678046924
Commun.13272808088646464
18261376160016001342137613521776231200280280
77565656
253192192
. 19228443416329293483232
17813012376
20065613512
Cubo 16Minimax
273220
20201300342336
35362256
760640
38402560
588592
35882442
361352
29241900342336
35362256
386368
35682288
940135213488080994
1704077681
998204856
Commun.220168176176198144144144
27281984198419842277186420961936583544512528165120120120583424408408
510446004172
113964316
17082312452
30348822940
Cubo 32Minimax
166158
1344864182176
17761136468384
19681328420374
20001360250244
18641224
182176
17761136250208
18081168758880838
10488646
1965516913
635123296
Commun.462304296296374272272272
371827042880283233882768272027361034864928928341248248248
1221848824824
700065606296
158285440
19696919812
43594034040
D-22
1•
Apéndice D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Tabla D-22: Resultados Algoritmo CA ME (Anillos)Num. Proc.Grafobina400_lbina400 11bina400_15bina400_5ring400_lring400_l 1ring400_15ring400_5torus400_ltorus400 11torus400 15torus400_5mesh400_lmesh400_l 1mesh400_15mesh400 5inout400 1inout400_l 1inout400 15inout400 5pipe400_lpipe400_l 1pipe400_15pipe400_5nbody399_lnbody399_l 1nbody399_15nbody399 5glg2g3g4g5g6g7g8g9
Anillo 8Minimax
408494
47703106662656
705644961168102474244864932
102866064294
764806
53763456662656
70564496
706688
7088452813952282234887601862
16445911915
1876708228
Commun.198120376432
88646464
21341536153615361463166418161928275200392376
77565656
253192192192
347637763616
123564320
12847514504
28106015744
Anillo 16Minimax
273260
20601340342336
353622561068864
40622778745864
36682592422404
28701940342336
35362256
386368
35682288120218941560
140401634
25773513825
1228466440
Commun.330240240240176128128128
51263616403238243113301634162600
704624
1072688165120120120517376376376
662073165952
217088320
25815123748
44700032984
Anillo 32Minimax
265246
1352898182176
177611361216928
25281888720672
22741664438330
20241384
182176
17761136226208
18081168152618401904
317682062
45605825601891966540
Commun.792600888736352256256256
985671687168716859295472634460002365172816881688341248248248
1045760760760
1400416060133404916817412
45622153292
80947266144
D-23
Apéndice E
IIIII Apéndice E
i
I• Resultados de función de coste y tiempos de ejecución
En este apéndice se muestran los resultados obtenidos en la ejecución simulada
I de los grafos DAGs. Para cada grafo se indica el valor de la función de coste minimaxobtenido a partir del algoritmo BOK_2, el volumen de cómputo máximo del grafo y eltiempo de ejecución obtenido en la simulación.
I
I
I
I
I
I
I
I
I
I
I
I
111111111111111111111
Apéndice E
Tabla E-l : Tiempos de ejecución en Arquitectura Full-Connected8 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilgl2
Minimax11991892183047921150
1250787891
158468634615361784
Cómputo Máximo751
135014603200
780883207039
125430420012901290
T ejecución760
1964395442241020
1442578552
350662469216581658
Tabla E-2: Tiempos de ejecución en Arquitectura Full-Connected16 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilg!2
Minimax680
109010584792
618125078
5377841023794
8961144
Cómputo Máximo280720730
1870370
84800
4201
662402260
650650
T ejecución381
11022460
3066600
1143735971
2257882672
10101010
Tabla E-3: Tiempos de ejecución en Arquitectura Full-Connected32 Procesadores
Grafoglg2g3g4g5g6g7g8g9gilg!2
Minimax406664634
4792462
1250785377
456562262
576824
Cómputo Máximo141370440950330
848002791
348801340330330
T ejecución261658
16223090
454889014854
1344681822764764
E-2
111111111111111111111
Apéndice E
Tabla E- 10: Tiempos de ejecución en Arquitectura Hipercubo8 Procesadores
Grafo
glg2g3g4g5g6g?g8g9gi lg!2
Minimax14822176217474721510
152865
10697
1844568110
15361784
Cómputo Máximo751
135014603200780
88320
7039125430
420012901290
T ejecución768
2002
397048001060
1442578845
351174
470016621662
Tabla E-l 1 : Tiempos de ejecución en Arquitectura Hipercubo1 6 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilg!2
Minimax991
1368
128877401080
1777047937
1075965658
8961144
Cómputo Máximo280720730
1870370
848004201
662402260
650650
T ejecución413
1198
2550
4650726
1145067264
2274602700
10461046
Tabla E-12: Tiempos de ejecución en Arquitectura Hipercubo32 Procesadores
Grafoglg2g3g4g5g6g7g8g9gi lg!2
Minimax722880834
9468646
1970666913
662163680
576824
Cómputo Máximo141370440950330
848002791
348801340330330
T ejecución293838
17307314
556892865648
139632
1808880880
E-5
•
111111111111111111111
Apéndice E
Tabla E-4: Tiempos de ejecución en Arquitectura Malla9 Procesadores
Grafo
glg2g3§4g5g6g7g8g9gio§11
Minimax1212
1852
18586760
1268142235
9160
1523306720
16001784
Cómputo Máximo440
1260
13402290
660883206575
111370
3980
12901290
T ejecución525
18083768
3370948
1443868374
3365224284
16781670
Tabla E-5: Tiempos de ejecución en Arquitectura Malla16 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gi lg!2
Minimax100813961304 •
77401080
177704
7937
1070165742
8961144
Cómputo Máximo280720730
1870370
84800
4201
662402260
650650
T ejecución423
1194
24923754692
114764
7387227964
268810261026
Tabla E-6: Tiempos de ejecución en Arquitectura Malla32 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilg!2
Minimax833940964
11156750
2214037425
680604290
576824
Cómputo Máximo141370440950330
848002791
348801340330330
T ejecución325884
17467954682
891606991
1420161830764764
E-3
111111'*1 ;
• t
•r:1
4lai i
'11M1^I J
11
1u1
Apéndice E
Tabla E-7: Tiempos de ejecución en Arquitectura Anillo8 Procesadores
Grafo
glg2g3g4g5g6g?g8g9gilg!2
Minimax16942404
2450
97281810
196590
13037
2006289252
15361784
Cómputo Máximo751
1350
14603200
78088320
7039
12543042001290
1290.
T ejecución772
20284014
55781082
144772
9133
35207047161658
1658
Tabla E-8: Tiempos de ejecución en Arquitectura Anillo16 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilg!2
Minimax140720961972
136361992
293468
13569150880
9260
8961144
Cómputo Máximo280720730
1870370
84800
420166240
2260
650650
T ejecución505
1242
26966826
826114377
8811
23072827401010
1010
Tabla E-9: Tiempos de ejecución en Arquitectura Anillo32 Procesadores
Grafo
glg2g3g4g5g6g7g8g9gilg!2
Minimax196518241796
269602062
45799211777
1512889514
576824
Cómputo Máximo141370440950330
848002791
348801340330330
T ejecución729
13842138
10142570
8980513862
1952961942764764
II
E-4