Tesis doctoral de Daniel Jiménez González
En esta tesis analizamos y presentamos algoritmos de ordenación secuencial y paralelo que explotan la jerarquía de memoria del computador usado y/o reducen la comunicación de los datos. Sin embargo, aunque los objetivos de esta tesis son los mismo que los de otros trabajos, la forma de conseguirlos es diferente. en esta tesis los conseguimos haciendo que los algoritmos de ordenación propuestos sean conscientes de la arquitectura del computador y las características de los datos que queremos ordenar. los conjuntos de datos que consideramos son conjuntos que caben en memoria principal, pero no en memoria cache. los algoritmos presentados se adaptan, en tiempo de ejecución, a las características de los datos (duplicados, con sesgo, etc.) Para evitar pérdidas de rendimiento dependiendo de estas características. Para ello, estos algoritmos realizan un particionado de los datos, utilizando una técnica que llamamos mutant reverse sorting y que presentamos en esta tesis. mutant reverse sorting se adapta dinámicamente a las características de los datos y del computador. Esta técnica analiza una muestra del conjunto de datos a ordenar para seleccionar la forma más rápida de particionar los datos. Esta técnica elige entre reverse sorting y counting split en función de la distribución de los datos. Estas técnicas también son propuestas en esta tesis. el análisis de estas técnicas, junto con los algoritmos de ordenación presentados, se realiza en un computador ibm basado en módulos p630 con procesadores power4 y en un computador sgi o2000 con procesadores r10k. En el análisis realizado para ambos computadores se presentan modelos de comportamiento que se comparan con ejecuciones reales. con todo ello, conseguimos los algoritmos de ordenación secuencial y paralelo más rápidos para las características de los datos y los computadores utilizados. esto es gracias a que estos algoritmos se adaptan a los computado
Datos académicos de la tesis doctoral «Algoritmos de ordenacion conscientes de la arquitectura y las caracteristicas de los datos.«
- Título de la tesis: Algoritmos de ordenacion conscientes de la arquitectura y las caracteristicas de los datos.
- Autor: Daniel Jiménez González
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 02/07/2004
Dirección y tribunal
- Director de la tesis
- Juan Navarro Guerrero
- Tribunal
- Presidente del tribunal: mateo Valero cortés
- Ana Ripoll (vocal)
- ricardo Baeza yates (vocal)
- ricard Gavaldí mestre (vocal)