2024-03-29T04:43:12Zhttps://www.tdx.cat/oai/requestoai:www.tdx.cat:10803/30302017-09-03T16:18:09Zcom_10803_120col_10803_122
TDX (Tesis Doctorals en Xarxa)
author
Roig Mateu, Concepció
authoremail
roig@eup.udl.es
authoremailshow
true
director
Ripoll Aracil, Ana
2011-04-12T14:11:34Z
2003-03-26
2002-07-24
8468811018
http://www.tdx.cat/TDX-0326103-190947http://hdl.handle.net/10803/3030
B.4.582-2003
En el momento de ejecutar una aplicación paralela, el programador (o el usuario) se enfrenta a decisiones importantes para reducir el tiempo de ejecución global, tales como cuántos procesadores ha de usar para ejecutar la aplicación y, dado un número de procesadores, cómo distribuir las tareas de la aplicación aprovechando al máximo su capacidad de concurrencia. Al problema de resolver la distribución de las tareas de una manera global se le conoce como el problema del mapping.<br/>En la literatura existen dos formas distintas de abordar el problema del mapping en función del conocimiento que se tiene de la aplicación. Cuando el comportamiento de la aplicación es conocido (o predecible) a priori, la asignación se realiza de forma estática (antes de la ejecución), y las tareas se ejecutan en el procesador asignado hasta que finalizan. Por el contrario, cuando el comportamiento de la aplicación no es predecible, la asignación se realiza de forma dinámica, y las tareas pueden cambiar de procesador durante la ejecución. <br/>En el presente trabajo nos centramos en el proceso de mapping estático. Para la realización de este proceso, el programa paralelo se suele representar mediante un modelo de grafo de tareas ponderado, que resume las características más relevantes estimadas del comportamiento de la aplicación. En función del tipo de aplicación, en la literatura se utilizan principalmente dos modelos de grafo. Para aplicaciones cuyas tareas se comunican únicamente por el principio y el final, el modelo, denominado TPG (Task Precedence Graph), refleja las comunicaciones y precedencias entre las tareas y el orden parcial de ejecución de las mismas. Cuando se trata de aplicaciones cuyas tareas tienen comunicaciones en cualquier punto, e incluso comunicaciones bidireccionales, en la literatura se utiliza un modelo simplificado, denominado TIG (Task Interaction Graph), en el que no se contemplan las precedencias y se asume que todas las tareas pueden ser simultáneas.<br/>Ahora bien, en los entornos actuales de paso de mensajes, el programador no está sujeto a ninguna restricción en cuanto a la ubicación de las primitivas de comunicación dentro de las tareas. Además, debido al tipo de problemas que se resuelven computacionalmente, existe en los últimos años un creciente interés en el desarrollo de aplicaciones formadas por un conjunto de tareas que realizan distintas funciones y que coordinan su ejecución mediante intercambios de información en cualquier punto dentro de las mismas.<br/>Para modelar el comportamiento de las aplicaciones con paralelismo de tareas, con un patrón de interacciones entre tareas arbitrario, se propone un nuevo modelo de grafo, denominado Temporal Task Interaction Graph (TTIG). Dicho modelo incluye un nuevo parámetro, denominado grado de paralelismo, que indica la máxima capacidad de concurrencia de las tareas que se comunican, en función de las dependencias provocadas por dichas comunicaciones.<br/>A partir del comportamiento obtenido de la aplicación, se propone un mecanismo para determinar las cotas teóricas mínima y máxima sobre el número de procesadores necesario para realizar su ejecución en un tiempo mínimo. <br/>A partir del modelo TTIG se definen nuevas políticas de mapping de distintas complejidades que realizan las asignaciones de tareas teniendo en cuenta la posibilidad de concurrencia entre las mismas que indica el grado de paralelismo.<br/>En los entornos actuales de paso de mensajes PVM y MPI, la política de mapping que se usa por defecto es una distribución de las tareas basada en el orden de activación de las mismas. Dada la simplicidad de este mecanismo, dichos entornos se mejoran integrando un proceso automático para la extracción del grafo TTIG y para aplicar una política de mapping basada en dicho modelo.Parallel programming presents the programmers (or the users) with daunting problems when attempting to achieve efficient execution. Two of these problems are to decide how many processors are necessary to execute the application and, for a specific number of processors, how to distribute the application tasks by exploiting their ability of concurrency, also known as the mapping problem.<br/>Mapping strategies can be classified as either static or dynamic, depending on the knowledge of the application. When the application has predictable run-time behaviour (i.e. the behaviour is loosely dependent on the input values), the mapping is carried out statically before execution. However, for applications whose run-time behaviour is not deterministic or not so predictable, performing mapping only once at the beginning is insufficient. For these cases the mapping is carried out dynamically during run-time.<br/>In this work, we focus on the static mapping problem. In order to accomplish the static mapping efficiently, the characteristics of the parallel program have to be known or estimated prior to execution. In this case, the application is represented in a task graph that summarizes the application behaviour.<br/>Depending on the characteristics of the application to be modelled, two distinct task graph models have been extensively used in the literature. The Task Precedence Graph (TPG), is a directed graph where nodes and arcs represent the tasks and the task precedence constraints respectively. This is effective for applications where interactions between tasks take place only at the beginning and at the end of their execution. On the other hand, distributed applications where the executing tasks are required to communicate during their lifetime rather than just at the initiation and at the end, are usually modelled in the literature by the Task Interaction Graph (TIG). This is an undirected graph that does not include temporal information and it is normally assumed that all the tasks may run in parallel.<br/>In current message-passing environments, the programmer has no restriction about the allocation of communication primitives inside tasks. Moreover, there is growing interest in the development of applications composed of a set of tasks carrying out different functions (i.e. with task parallelism) that coordinate one to each other through message transference at any point inside them.<br/>To model these applications that have an arbitrary task interaction pattern, we propose a new task graph model, called Temporal Task Interaction Graph (TTIG), that captures temporal information about parallel programs with a new parameter called degree of parallelism. This gives information about the potential concurrency that each pair of adjacent tasks can achieve, according to their mutual dependencies.<br/>From the definition of the application behaviour, a heuristic method is proposed to determine the theoretical maximum and minimum number of processors that are necessary to execute the application in the minimum time.<br/>Starting from the TTIG model, two new mapping algorithms are defined with different complexities, that carry out the allocation according to the ability of concurrency of tasks indicated by the degree of parallelism.<br/>In current message-passing environments PVM and MPI, the processor mapping mechanism is based on simply heuristics that take decisions independently of the relationship exhibited by tasks. Thus, these environments are enhanced by integrating an automatic mechanism to extract the TTIG for a given application, and to apply a mapping heuristic based on the model.
spa
Mapping
Aplicacions paral.leles
Sistemes distribuïts
Algoritmos de asignación basados en un nuevo modelo de representación de programas paralelos
info:eu-repo/semantics/doctoralThesis info:eu-repo/semantics/publishedVersion
URL
https://www.tdx.cat/bitstream/10803/3030/1/crm01de13.pdf
File
MD5
f83f6708907c9bbc599c60500b4fd9fa
426897
application/pdf
crm01de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/2/crm02de13.pdf
File
MD5
19e2473e07ded1c69a2862a23746fe38
344430
application/pdf
crm02de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/3/crm03de13.pdf
File
MD5
0ae02ee87960ff9e75eb0b215285d26b
466040
application/pdf
crm03de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/4/crm04de13.pdf
File
MD5
e6b1f6d66962253a8a9ead1da5a6d473
430931
application/pdf
crm04de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/5/crm05de13.pdf
File
MD5
3eff24185e22cbcc1b732fc885c3eec1
403604
application/pdf
crm05de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/6/crm06de13.pdf
File
MD5
d2fc7bb87728e9df600e189767d2247e
469157
application/pdf
crm06de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/7/crm07de13.pdf
File
MD5
fdf3e6af2761a3a7653c9aac023ae0e2
304318
application/pdf
crm07de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/8/crm08de13.pdf
File
MD5
fbacf3aba6f1eba202b6fe18ea9c2127
618743
application/pdf
crm08de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/9/crm09de13.pdf
File
MD5
0239185eacb9f48b928e8ed735e26778
482046
application/pdf
crm09de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/10/crm10de13.pdf
File
MD5
56b0338122082ebb9a077565d6af944d
525206
application/pdf
crm10de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/11/crm11de13.pdf
File
MD5
20c96e4f8639a8bcead354f2fe2ff776
366188
application/pdf
crm11de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/12/crm12de13.pdf
File
MD5
b439b577099d628f9645767cbaef68bf
483574
application/pdf
crm12de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/13/crm13de13.pdf
File
MD5
78bc00af65f55f5499bbc5319eb1b26a
470820
application/pdf
crm13de13.pdf
URL
https://www.tdx.cat/bitstream/10803/3030/14/crm13de13.pdf.txt
File
MD5
e8533da1dd4ff80a01500dae7d9aac4a
36779
text/plain
crm13de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/15/crm12de13.pdf.txt
File
MD5
ba114c4b74e7762e414572cefc551fe2
15213
text/plain
crm12de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/16/crm11de13.pdf.txt
File
MD5
254b20e9bd4cdc84f5a3acad0af8087a
26452
text/plain
crm11de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/17/crm10de13.pdf.txt
File
MD5
a611f8a8444d09a91955c1ebd1a7af85
11907
text/plain
crm10de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/18/crm09de13.pdf.txt
File
MD5
46d1ea3326eace70929a3a397d5c2a9a
11264
text/plain
crm09de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/19/crm08de13.pdf.txt
File
MD5
f47fb26617b03739451df2ff7cec0a33
11973
text/plain
crm08de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/20/crm07de13.pdf.txt
File
MD5
0d9db43191ef14260dfe7e548f221cb1
14629
text/plain
crm07de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/21/crm06de13.pdf.txt
File
MD5
114151ebb565cc947ff810f47bae01a5
22072
text/plain
crm06de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/22/crm05de13.pdf.txt
File
MD5
67db194ac7f25853e98c66e72668d492
58902
text/plain
crm05de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/23/crm04de13.pdf.txt
File
MD5
e045dd75d2af7260c44e926687345a2f
27699
text/plain
crm04de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/24/crm03de13.pdf.txt
File
MD5
4172f99c16601417f822d84ae128fee9
34520
text/plain
crm03de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/25/crm02de13.pdf.txt
File
MD5
6e4dee89adfcb45705ba8ef85c052c41
36336
text/plain
crm02de13.pdf.txt
URL
https://www.tdx.cat/bitstream/10803/3030/26/crm01de13.pdf.txt
File
MD5
66cb73f57b1ecc345121e24fdf6cf401
40449
text/plain
crm01de13.pdf.txt