Algoritmo paralelo - Estructura
Para aplicar cualquier algoritmo correctamente, es muy importante que seleccione una estructura de datos adecuada. Esto se debe a que una operación particular realizada en una estructura de datos puede llevar más tiempo en comparación con la misma operación realizada en otra estructura de datos.
Example- Para acceder a la i ésimo elemento en un conjunto mediante el uso de una matriz, que puede tomar un tiempo constante, pero mediante el uso de una lista enlazada, el tiempo requerido para realizar la misma operación puede llegar a ser un polinomio.
Por tanto, la selección de una estructura de datos debe hacerse considerando la arquitectura y el tipo de operaciones a realizar.
Las siguientes estructuras de datos se utilizan comúnmente en la programación paralela:
- Lista enlazada
- Arrays
- Red de hipercubo
Lista enlazada
Una lista enlazada es una estructura de datos que tiene cero o más nodos conectados por punteros. Los nodos pueden ocupar o no ubicaciones de memoria consecutivas. Cada nodo tiene dos o tres partes: unadata part que almacena los datos y los otros dos son link fieldsque almacenan la dirección del nodo anterior o siguiente. La dirección del primer nodo se almacena en un puntero externo llamadohead. El último nodo, conocido comotail, generalmente no contiene ninguna dirección.
Hay tres tipos de listas vinculadas:
- Lista individualmente vinculada
- Lista doblemente vinculada
- Lista enlazada circular
Lista individualmente vinculada
Un nodo de una lista enlazada individualmente contiene datos y la dirección del siguiente nodo. Un puntero externo llamadohead almacena la dirección del primer nodo.
Lista doblemente vinculada
Un nodo de una lista doblemente enlazada contiene datos y la dirección del nodo anterior y del siguiente. Un puntero externo llamadohead almacena la dirección del primer nodo y el puntero externo llamado tail almacena la dirección del último nodo.
Lista enlazada circular
Una lista enlazada circular es muy similar a la lista enlazada individual, excepto por el hecho de que el último nodo guardó la dirección del primer nodo.
Matrices
Una matriz es una estructura de datos donde podemos almacenar tipos de datos similares. Puede ser unidimensional o multidimensional. Las matrices se pueden crear de forma estática o dinámica.
En statically declared arrays, la dimensión y el tamaño de las matrices se conocen en el momento de la compilación.
En dynamically declared arrays, la dimensión y el tamaño de la matriz se conocen en tiempo de ejecución.
Para la programación de memoria compartida, las matrices se pueden usar como una memoria común y para la programación en paralelo de datos, se pueden usar particionando en submatrices.
Red de hipercubo
La arquitectura de hipercubo es útil para aquellos algoritmos paralelos donde cada tarea tiene que comunicarse con otras tareas. La topología de hipercubo puede incorporar fácilmente otras topologías como anillo y malla. También se conoce como n-cubos, dondenes el número de dimensiones. Un hipercubo se puede construir de forma recursiva.
