Control de granularidad en la ejecución paralela de programas lógicas mediante técnicas de análisis y transformación

López García, Pedro (1999). Control de granularidad en la ejecución paralela de programas lógicas mediante técnicas de análisis y transformación. Thesis (Doctoral), Facultad de Informática (UPM).

Description

Title: Control de granularidad en la ejecución paralela de programas lógicas mediante técnicas de análisis y transformación
Author/s:
  • López García, Pedro
Contributor/s:
  • Hermenegildo Salinas, Manuel
Item Type: Thesis (Doctoral)
Date: September 1999
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview

Abstract

Los lenguajes de programación lógica ofrecen un excelente marco para la aplicación de técnicas de paralelización automática. Existen resultados teóricos que pueden asegurar cuando los programas paralelizados son correctos, es decir, obtienen los mismos resultados que los correspondientes secuenciales y cuando la ejecución de los primeros no tarda más tiempo que la de los segundos. Sin embargo dichos resultados suponen un entorno ideal de ejecución paralela y no tienen en cuenta que en la práctica existen una serie de costes asociados con la ejecución paralela de tareas, como por ejemplo creación y gestión de tareas, posible migración de tareas a procesadores remotos, costes de comunicación, etc. Dichos costes pueden dar lugar a que la ejecución de los programas paralelos sea más lenta que la de los secuenciales o al menos limitar la ganancia debida al paralelismo introducido. En esta tesis hemos desarrollado completamente e integrado en un sistema avanzado de manipulación de programas que realiza análisis y optimización de los mismos un sistema automático de control de granularidad para programas lógicos que estima eficientemente la granularidad de las tareas (e.d., el trabajo necesario para su ejecución completa) y la usa para limitar el paralelismo de forma que se controla el efecto de los costes mencionados anteriormente. El sistema está basado en un esquema de análisis y transformación de programas, en el cual se realiza tanto trabajo como sea posible en tiempo de compilación para evitar añadir nuevos costes a la ejecución de los programas. En la realización de la transformación de programas se persigue el objetivo de minimizar el trabajo adicional hecho en tiempo de ejecución, para lo que hemos propuesto una serie de técnicas mientras que en el análisis el objetivo es obtener la información necesaria para esta fase de transformación, lo que nos ha llevado a desarrollar varios tipos de análisis capaces de inferir informaciones tales como cotas del coste de procedimientos qué llamadas a procedimientos no fallarán, etc. El coste adicional en tiempo de ejecución asociado con la técnica que proponemos es usualmente bastante pequeño. Además realizamos un análisis estático del coste asociado con el proceso de control de granularidad, de forma que se pueda, decidir su conveniencia. Es interesante resaltar que muchas de las técnicas que hemos desarrollado tienen otras aplicaciones importantes, además del mencionado control de granularidad entre otras: eliminación de paralelismo especulativo, detección de errores de programación, varias aplicaciones relacionadas con la transformación de programas, por ejemplo, reordenación de objetivos o ayuda a los sistemas de transformación de programas a elegir las transformaciones óptimas, eliminación de recursividad, selección de diferentes algoritmos o reglas de control cuya eficiencia puede depender de los tamaños de los datos de entrada, depuración de eficiencia (optimización) de programas y la optimización de consultas a bases de datos deductivas. Finalmente, los resultados experimentales realizados con un prototipo del sistema, han mostrado que el control de granularidad puede contribuir sustancialmente a la optimización de la ejecución en paralelo de programas, especialmente en sistemas distribuidos y que parece bastante factible un enfoque automático del mismo.

More information

Item ID: 198
DC Identifier: http://oa.upm.es/198/
OAI Identifier: oai:oa.upm.es:198
Deposited by: Archivo Digital UPM
Deposited on: 13 Sep 2007
Last Modified: 20 Apr 2016 06:07
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM