Algoritmos de ordenación paralela basados en la técnica divide y vencerás

  1. Almeida Rodriguez, Francisco
  2. Rodríguez, R.
  3. Rodríguez León, Casiano
  4. García López, Félix César
  5. Roda García, José Luis
  6. Morales González, Domingo
Livre:
II Jornadas de informática. Actas: Almuñécar (Granada), 15 al 19 de julio 1996
  1. Clares Rodríguez, Buenaventura (dir. congr.)

Éditorial: [Almuñécar?] : Asociación Española de Informática y Automática, [1996]

ISBN: 84-8254-080-7

Année de publication: 1996

Pages: 233-244

Congreso: Jornadas de Informática (2. 1996. Almuñécar)

Type: Communication dans un congrès

Résumé

La ordenación de secuencias de datos es una actividad habitual en el procesamiento de datos y de informacion. Desde el punto de vista secuencial el problema ha sido ampliamente investigado y los estudios teóricos y prácticos presentados por muchos autores permiten elegir la propuesta algorítmica adecuada para cada situación. Sin embargo, en el contexto de la computación en paralelo la enorme variedad de propuestas en cuanto a modelos computacionales, arquitectura y algoritmos, no permiten obtener una idea clara acerca de cual puede ser la mejor opción. Describimos en este trabajo la paralelización de algoritmos secuenciales clásicos (quicksort, mergesort, heapsort) apoyándonos en la técnica Divide y Vencerás paralela. El estudio se realiza para multicomputadores basados en el modelo de intercambio de mensajes a través de una red de interconexión. Se desarrollan los análisis teóricos y la experiencias computacionales de las distintas variantes sobre tres tipologías: árbol, hipercubo y n-grafo. Presentamos los resultados computacionales obtenidos de la implementación de tales algoritmos sobre redes de transputers y extraemos conclusiones a cerca de la mejor alternativa en cada caso.