A Study of Software Primitives in the context of Concurrent Data Structures

Abstract

The "free ride" towards faster processor speeds at the pace set by Moore’s Law has come to an end. Cramming ever smaller transistors on the same processor has reached a physical limit, and quantum technology is yet too immature to take on the challenge. Multiprocessor architectures have surged to meet the rising demand for computational power that has arisen in recent years. These architectures are capable of outperforming single-core architectures, but they require meticulous and orderly resource management to do so in a cost-efficient manner. This is where Concurrent Data Structures come to play. The new ultimate goal is to provide data structure designs that transparently manage workload balancing through several processors, ensuring correctness as well as versatility in a variety of concurrent settings. In this context, we approach the subject of providing the building blocks for Concurrent Data Structures: software and hardware synchronisation primitives. These are the operations in charge of the most critical functionalities of concurrent programs, those having to do with shared-resource management. Synchronisation primitives have to satisfy specific constraints related to correctness conditions for concurrent executions, and are therefore delicate matters worthy of unhurried study. In particular, we dive into the algorithmic details concerning the Non-blocking K-Compare-Single-Swap (KCSS) primitive proposed at (Luchangco et al., 2008), a non- blocking obstruction-free software primitive aimed at meeting the challenges posed by Concurrent Linked Data Structures. We provide a profuse educational guide through every non-trivial design feature of KCSS culminating in the proposal of a fully-functional, efficient and transparent-to-the-user C++ implementation, as well as usage instructions.El ”viaje gratuito” en el aceleramiento de las velocidades de procesado al ritmo establecido por la Ley de Moore ha llegado a su fin. La integración de transistores cada vez más pequeños en un mismo procesador ha alcanzado un límite físico, y la tecnología cuántica es aún demasiado inmadura para asumir el desafío. Las arquitecturas multiprocesador han surgido para satisfacer la creciente demanda de poder computacional que ha surgido en los últimos años. Estas arquitecturas son capaces de superar a las arquitecturas de un solo núcleo, pero requieren una gestión de recursos meticulosa y ordenada para hacerlo de manera rentable. Aquí es donde entran en juego las Estructuras de Datos Concurrentes. El nuevo objetivo final es proporcionar diseños de estructuras de datos que gestionen de forma transparente el equilibrado de la carga de trabajo entre procesadores, asegurando corrección y versatilidad en distintos escenarios de concurrencia. En este contexto, abordamos el tema de proporcionar los componentes básicos para la construcción de Estructuras de Datos Concurrentes: las primitivas software y hardware de sincronización. Estas son las operaciones encargadas de las funcionalidades críticas de los programas concurrentes, las que tienen que ver con la gestión de recursos compartidos. Las primitivas de sincronización tienen que satisfacer restricciones específicas relacionadas con las condiciones de corrección para ejecuciones concurrentes y, por lo tanto, son asuntos delicados merecedores de un estudio de- tallado. En particular, profundizamos en los detalles algorítmicos relacionados con la primitiva K-Compare-Single-Swap sin bloqueo (KCSS) propuesta en (Luchangco et al., 2008), una primitivo en software sin bloqueo (non-blocking en inglés) y libre de obstrucciones (obstruction-free) destinada a afrontar los desafíos planteados por las Estructuras de Datos Enlazadas Concurrentes. Aportamos una guía educativa acerca de las decisiones de diseño no triviales de KCSS, que culmina con la propuesta de una implementación en C++ funcional, eficiente y transparente para el usuario, así como sus instrucciones de uso.