Generación de grafos dirigidos acíclicos mediante métodos aleatorios para la planificación de tareas

Directed Acyclic Graphs (DAGs) are used in different areas of scientific research. In the area of computing, they serve to represent tasks (programs) constituted by underlying subtasks (subprograms) that can be executed in different processors in a distributed environment. The DAGs are generated by different methods that produce them in a random way, to create synthetic loads that make it easier to test new task planning algorithms in parallel and distributed computing systems. The planning of tasks, is a problem that has been addressed with different programming techniques to optimize the resources of computer systems. Although they are very elaborate techniques and methods, most of them lack an analysis prior to the planning of the DAG. Therefore, in this work, we describe six methods for the random generation of DAGs; Two of these methods are selected to experiment with the generation of random DAGs, with the objective of carrying out a preliminary analysis of each of the DAGs and subsequently construct synthetic loads that will be used as input structures, in a new algorithm for planning and assignment of tasks, in a Distributed Heterogeneous Computing System (DHCS). To the produced DAGs, which constitute the synthetic load, the width of the graph is evaluated, because it is one of the most incidents characteristics in the planning and allocation process. The results obtained show that each of the methods produces DAGs with totally dissimilar graph widths. Keywords: Directed Acyclic Graph (DAG), Heterogeneous Distributed Computer System (HDCS), Algorithm for scheduling and assigning tasks in a HDCS, Parallel Tasks.Los Grafo Dirigidos Acíclicos (DAGs, por sus siglas en inglés Directed Acyclic Graph) se utilizan en diferentes áreas de la investigación científica. En el área de la computación, sirven para representar tareas (programas) constituidas por subtareas subyacentes (subprogramas) que pueden ser ejecutados en diferentes procesadores en un ambiente distribuido. Los DAGs, se generan mediante diferentes métodos que los producen de forma aleatoria, para crear cargas sintéticas que facilitan probar nuevos algoritmos de planificación de tareas en sistemas de cómputo paralelo y distribuido. La planificación de tareas, es un problema que se ha abordado con diferentes técnicas de programación para optimizar los recursos de los sistemas de cómputo. Aunque son técnicas y métodos muy elaborados, en su mayoría carecen de un análisis previo a la planificación de los DAG. Por lo anterior, en este trabajo se describen seis métodos para la generación aleatoria de DAGs; se seleccionan dos de estos métodos para experimentar la generación de aleatoria de DAGs, con el objetivo de realizar un análisis previo de cada uno de los DAGs y posteriormente construir cargas sintéticas que serán utilizadas como estructuras de entrada, en un nuevo algoritmo para la planificación y la asignación de tareas, en un Sistema de Cómputo Heterogéneo Distribuido (SCHD). A los DAGs producidos, que constituyen la carga sintética, se evalúa la anchura del grafo, debido a que es una de las características más incidentes en el proceso de la planificación y la asignación. Los resultados obtenidos muestran que, cada uno de los métodos produce DAGs con anchuras de grafo totalmente disímiles