¿Podemos predecir en algoritmos paralelos no deterministas?

Résumé

Esta Tesis intenta dar un paso adelante en un ámbito poco explorado. La misma presenta una nueva metodología práctica para la predicción de rendimiento de aplicaciones dependientes de los datos en un computador paralelo, lo cual refleja un comportamiento no determinista.Dichas aplicaciones deben cumplir con determinadas características tales como requerir el cálculo masivo y estar preparadas para trabajar en paralelo con todo lo que esto involucra (sincronización, comunicación). La idea de trabajar en este sentido surge de la necesidad de dar respuesta a un número de aplicaciones paralelas frecuentes que normalmente son dejadas a un lado. Cualquier aporte en el área no determinista por mínima que sea representa un gran avance ante la falta de conocimiento general. No sólo hay que pensar en el problema que se resuelve sino en el beneficio que representa para la familia de problemas que contiene al problema resuelto.La propuesta parte de ciertas premisas y utiliza la ciencia computacional para extraer conocimiento de los experimentos diseñados (datos de entrada), en una primera fase, y luego proporciona un mecanismo de predicción que resulta bastante prometedor, en una segunda fase. La formulación de las hipótesis, la composición de los experimentos, la ejecución de la aplicación estudiada, el proceso de descubrir conocimiento, la interpretación del modelo y la evaluación de calidad son las etapas que forman parte de la fase de extracción del conocimiento, mientras que la etapa de comparación de datos pertenece a la fase de predicción. Una aplicación representativa dependiente de los datos de entrada es el problema del viajante (TSP), donde es difícil predecir el tiempo de ejecución por depender fuertemente del conjunto de ciudades de entrada. Este problema es de considerable significación no sólo desde el punto de vista teórico. Hay muchos casos importantes de problemas prácticos que pueden ser formulados como problemas TSP y muchos o