dsc. i - dipòsit digital de documents de la uab• en cuarto lugar, a partir de las salidas...

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



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


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


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


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


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



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


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



• 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



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


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


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


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


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


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


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)


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


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)


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)


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)


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)


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


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


Minimax991

1368

128877401080

1777047937

1075965658

8961144


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


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


Grafo

glg2g3g4g5g6g7g8g9gi lg!2

Minimax100813961304 •

77401080

177704

7937

1070165742

8961144


1870370

84800

4201

662402260

650650

T ejecución423

1194

24923754692

114764

7387227964

268810261026


Grafo


Minimax833940964

11156750

2214037425

680604290

576824


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


Grafo


Minimax140720961972

136361992

293468

13569150880

9260

8961144


1870370

84800

420166240

2260

650650

T ejecución505

1242

26966826

826114377

8811

23072827401010

1010


Grafo


Minimax196518241796

269602062

45799211777

1512889514

576824


848002791

348801340330330

T ejecución729

13842138

10142570

8980513862

1952961942764764

II

E-4

dsc. i - dipòsit digital de documents de la uab• en cuarto lugar, a partir de las salidas...

Documents