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 computadores y las características de los datos mejor que el resto de algoritmos analizados.Así, por un lado, el algoritmo secuencial propuesto, SKC-Radix sort, consigue unas mejoras de rendimiento de más de 25% comparado con los mejores algoritmos que encontramos en la literatura. Es más, cuanto mayor es el número de duplicados o el sesgo de los datos, mayor es la mejora alcanzada por el SKC-Radix sort.Por otro lado, el algoritmo paralelo presentado, PSKC-Radix sort, es capaz de ordenar hasta 4 veces más datos que Load Balanced Radix sort en la misma cantidad de tiempo. Load Balanced Radix sort era el algoritmo más rápido de ordenación en memoria y en paralelo para los conjunto de datos que ordenamos hasta la publicación de nuestros trabajos. / In this thesis we analyze and propose parallel and sequential sorting algorithms that exploit the memory hierarchy of the computer used and/or reduce the data communication. So, the objectives of this thesis are not different from the objectives of other works. However, the way to achieve those objectives is different.We achieve those objectives by being conscious of the computer architecture and the data characteristics of the data set we want to sort.We have focused on the data sets that fit in main memory but not in cache.So, the sorting algorithms that we present take into account the data characteristics (duplicates, skewed data, etc.) in order to avoid any lose of performance in execution time depending on those characteristics. That is done by partitioning the data set using Mutant Reverse Sorting, which is a partition technique that we propose in this thesis.Mutant Reverse Sorting dynamically adapts to the data characteristics and the computer architecture. This technique analyzes a set of samples of the data set to choose the best way to partition this data set. This chooses between Reverse Sorting and Counting Split, which are selected depending on the data distribution. Those techniques are also proposed in this thesis.The analysis of the partitioning techniques and the sorting algorithms proposed is done in an IBM computer based on p630 nodes with Power4 processors and in a SGI O2000 with R10K processors. Also, we present models of the behavior of the algorithms for those machines.The sequential and parallel algorithms proposed are the fastest for the computer architectures and data set characteristics tested. That is so because those algorithms adapt to the computer architecture and data characteristics better than others.On one hand, the sequential sorting algorithm presented, SKC-Radix sort, achieves performance improvements of more than 25% compared to other sequential algorithms found in the literature. Indeed, the larger the number of duplicates or data skew, the larger the improvement achieved by SKC-Radix sort. On the other hand, the parallel sorting algorithm proposed, PSKC-Radix sort, sorts 4 times the number of keys that Load Balanced Radix can sort in the same amount of time. Load Balanced Radix sort was the fastest in-memory parallel sorting algorithm for the kind of data set we focus on.
| Identifer | oai:union.ndltd.org:TDX_UPC/oai:www.tdx.cat:10803/5982 |
| Date | 02 July 2004 |
| Creators | Jiménez González, Daniel |
| Contributors | Larriba Pey, Josep Lluís, Navarro, Juan J. (Juan José), Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors |
| Publisher | Universitat Politècnica de Catalunya |
| Source Sets | Universitat Politècnica de Catalunya |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs. |
Page generated in 0.0018 seconds