A concurrent red black tree.
Loading...
Files
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La necesidad de tener estructuras de datos capaces de soportar varios procesos ha crecido con la masificación de los computadores multiprocesadores. Las estructuras de datos concurrentes buscan proveer una eficiencia similar a las estructuras de datos secuenciales permitiendo además el acceso concurrente a varios procesos y proveyendo mecanismos de sincronización transparentemente a esos procesos. Los árboles rojo negros son una importante estructura de datos utilizada en muchos sistemas. Lamentablemente ha sido complejo implementar un árbol rojo negro concurrente eficiente para computadores de memoria compartida.
Debido a esto la mayoría de los esfuerzos de investigación han sido dirigidos hacia otras estructuras de datos tipo diccionarios, principalmente skiplists y arboles AVL. En esta tesis presentamos un nuevo tipo de árbol rojo negro concurrente que utiliza técnicas de optimistic concurrency and nuevas operaciones de balance para escalar eficientemente y soportar contención. Nuestro árbol se comporta favorablemente comparado con otros diccionarios similares. En particular, en escenarios de alta contención se comporta hasta 14% mejor que la solución más conocida de los diccionarios concurrentes.
Debido a esto la mayoría de los esfuerzos de investigación han sido dirigidos hacia otras estructuras de datos tipo diccionarios, principalmente skiplists y arboles AVL. En esta tesis presentamos un nuevo tipo de árbol rojo negro concurrente que utiliza técnicas de optimistic concurrency and nuevas operaciones de balance para escalar eficientemente y soportar contención. Nuestro árbol se comporta favorablemente comparado con otros diccionarios similares. En particular, en escenarios de alta contención se comporta hasta 14% mejor que la solución más conocida de los diccionarios concurrentes.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2012