Cree punteros inteligentes expresivos para memoria remota en C ++

Hola Habr!

Hoy publicamos una traducción de un interesante estudio sobre cómo trabajar con memoria y punteros en C ++. El material es un poco académico, pero obviamente será de interés para los lectores de los libros de Galowitz y Williams .

Sigue el anuncio!

En la escuela de posgrado, me dedico a la construcción de estructuras de datos distribuidos. Por lo tanto, la abstracción que representa el puntero remoto es extremadamente importante en mi trabajo para crear código limpio y ordenado. En este artículo, explicaré por qué se necesitan punteros inteligentes, explicaré cómo escribí objetos de puntero remotos para mi biblioteca en C ++, me aseguraré de que funcionen exactamente como los punteros normales de C ++; Esto se hace utilizando objetos de enlace remoto. Además, explicaré en qué casos esta abstracción falla por la simple razón de que mi propio puntero (hasta ahora) no hace frente a esas tareas que pueden hacer los punteros comunes. Espero que este artículo interese a los lectores involucrados en el desarrollo de abstracciones de alto nivel.

API de bajo nivel

Cuando trabaja con computadoras distribuidas o con hardware de red, a menudo tiene acceso de lectura y escritura a una pieza de memoria a través de la API C. Un ejemplo de este tipo es la API MPI para la comunicación unidireccional. Esta API utiliza funciones que abren el acceso directo para leer y escribir desde la memoria de otros nodos ubicados en un clúster distribuido. Así es como se ve de una manera ligeramente simplificada.

void remote_read(void* dst, int target_node, int offset, int size); void remote_write(void* src, int target_node, int offset, int size); 

En el desplazamiento indicado en el segmento de memoria compartida del nodo de destino, remote_read una cierta cantidad de bytes de él y remote_write escribe una cierta cantidad de bytes.

Estas API son excelentes porque nos dan acceso a primitivas importantes que nos son útiles para implementar programas que se ejecutan en un grupo de computadoras. También son muy buenos porque funcionan realmente rápido y reflejan con precisión las capacidades ofrecidas a nivel de hardware: acceso remoto directo a memoria (RDMA). Las redes de supercomputadoras modernas, como Cray Aries y Mellanox EDR , nos permiten calcular que el retraso en la lectura / escritura no excederá de 1-2 μs. Este indicador se puede lograr debido al hecho de que la tarjeta de red (NIC) puede leer y escribir directamente en la RAM, sin esperar a que la CPU remota se active y responda a su solicitud de red.

Sin embargo, tales API no son tan buenas en términos de programación de aplicaciones. Incluso en el caso de API tan simples como las descritas anteriormente, no cuesta nada borrar datos accidentalmente, ya que no hay un nombre separado para cada objeto específico almacenado en la memoria, solo un búfer contiguo grande. Además, la interfaz no está tipificada, es decir, se le priva de otra ayuda tangible: cuando el compilador jura, si escribe el valor del tipo incorrecto en el lugar incorrecto. Su código simplemente resultará estar equivocado, y los errores serán de la naturaleza más misteriosa y catastrófica. La situación es aún más complicada porque en realidad estas API son un poco más complicadas, y cuando se trabaja con ellas es muy posible reorganizar por error dos o más parámetros.

Punteros eliminados

Los punteros son un nivel de abstracción importante y necesario al crear herramientas de programación de alto nivel. El uso de punteros directamente a veces es difícil, y puede hacer muchos errores, pero los punteros son los bloques de construcción fundamentales del código. Las estructuras de datos e incluso los enlaces de C ++ a menudo usan punteros debajo del capó.

Si suponemos que tendremos una API similar a las descritas anteriormente, una ubicación única en la memoria se indicará mediante dos "coordenadas": (1) el rango o ID del proceso y (2) el desplazamiento realizado en la parte compartida de la memoria remota ocupada por el proceso con este rango . No puedes detenerte allí y hacer una estructura completa.

  template <typename T> struct remote_ptr { size_t rank_; size_t offset_; }; 

En esta etapa, ya es posible diseñar una API para leer y escribir en punteros remotos, y esta API será más segura que la que usamos originalmente.

  template <typename T> T rget(const remote_ptr<T> src) { T rv; remote_read(&rv, src.rank_, src.offset_, sizeof(T)); return rv; } template <typename T> void rput(remote_ptr<T> dst, const T& src) { remote_write(&src, dst.rank_, dst.offset_, sizeof(T)); } 

Las transferencias en bloque se parecen mucho, y aquí las omito por brevedad. Ahora, para leer y escribir valores, puede escribir el siguiente código:

  remote_ptr<int> ptr = ...; int rval = rget(ptr); rval++; rput(ptr, rval); 

Ya es mejor que la API original, ya que aquí trabajamos con objetos escritos. Ahora no es tan fácil escribir o leer un valor del tipo incorrecto o escribir solo una parte de un objeto.

Aritmética de puntero

La aritmética de puntero es la técnica más importante que permite a un programador administrar colecciones de valores en la memoria; Si estamos escribiendo un programa para el trabajo distribuido en la memoria, presumiblemente vamos a operar con grandes colecciones de valores.
¿Qué significa aumentar o disminuir un puntero eliminado en uno? La opción más simple es considerar la aritmética de los punteros eliminados como la aritmética de los punteros ordinarios: p + 1 simplemente apunta al siguiente tamaño de memoria alineada sizeof(T) después de p en el segmento compartido del rango original.

Aunque esta no es la única definición posible de la aritmética de punteros remotos, recientemente se ha adoptado de manera más activa, y los punteros remotos utilizados de esta manera están contenidos en bibliotecas como UPC ++ , DASH y BCL. Sin embargo, el lenguaje Unified Parallel C (UPC), que ha dejado un rico legado en la comunidad de especialistas en informática de alto rendimiento (HPC), contiene una definición más elaborada de aritmética de puntero [1].

Implementar la aritmética del puntero de esta manera es simple, y solo implica cambiar el desplazamiento del puntero.

  template <typename T> remote_ptr<T> remote_ptr<T>::operator+(std::ptrdiff_t diff) { size_t new_offset = offset_ + sizeof(T)*diff; return remote_ptr<T>{rank_, new_offset}; } 

En este caso, tenemos la oportunidad de acceder a matrices de datos en memoria distribuida. Por lo tanto, podríamos lograr que cada proceso en el programa SPMD realice una operación de escritura o lectura en su variable en la matriz a la que se dirige el puntero remoto [2].

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { rput(ptr + my_rank(), my_rank()); } } 

También es fácil implementar otros operadores, proporcionando soporte para el conjunto completo de operaciones aritméticas realizadas en la aritmética de puntero ordinario.

Seleccione nullptr

Para punteros regulares, el valor nullptr es NULL , lo que generalmente significa reducir #define a 0x0, ya que es poco probable que se use esta sección en la memoria. En nuestro esquema con punteros remotos, podemos seleccionar un valor de puntero específico como nullptr , haciendo que esta ubicación en la memoria no se use, o incluir un miembro booleano especial que indicará si el puntero es nulo. A pesar de que hacer que una determinada ubicación en la memoria no se use no es la mejor solución, también tendremos en cuenta que al agregar solo un valor booleano, el tamaño del puntero remoto se duplicará desde el punto de vista de la mayoría de los compiladores y crecerá de 128 a 256 bits para mantener la alineación. Esto es especialmente indeseable. En mi biblioteca, elegí {0, 0} , es decir, un desplazamiento de 0 con un rango de 0, como el valor nullptr .

Es posible elegir otras opciones para nullptr que funcionarán igual de bien. Además, en algunos entornos de programación, como UPC, se implementan punteros estrechos que se ajustan a 64 bits cada uno. Por lo tanto, se pueden usar en operaciones de comparación atómica con intercambio. Al trabajar con un puntero estrecho, debe comprometerse: el identificador de desplazamiento o el identificador de rango deben caber en 32 bits o menos, y esto limita la escalabilidad.

Enlaces eliminados

En lenguajes como Python, la declaración de corchete sirve como azúcar sintáctica para llamar a los __getitem__ __setitem__ y __getitem__ , dependiendo de si lees el objeto o le escribes. En C ++, el operator[] no distingue a cuál de las categorías de valores pertenece un objeto y si el valor devuelto estará inmediatamente bajo lectura o escritura. Para resolver este problema, las estructuras de datos de C ++ devuelven enlaces que apuntan a la memoria contenida en el contenedor, que se puede escribir o leer. La implementación del operator[] para std::vector podría verse así.

  T& operator[](size_t idx) { return data_[idx]; } 

El hecho más significativo aquí es que devolvemos una entidad de tipo T& , que es un enlace en bruto de C ++ por el que puede escribir, y no una entidad de tipo T , que simplemente representa el valor de los datos de origen.

En nuestro caso, no podemos devolver un enlace en bruto de C ++, ya que nos estamos refiriendo a la memoria ubicada en otro nodo y no representada en nuestro espacio de direcciones virtuales. Es cierto que podemos crear nuestros propios objetos de referencia personalizados.
Un enlace es un objeto que sirve como envoltorio alrededor de un puntero, y realiza dos funciones importantes: se puede convertir a un valor de tipo T , y también puede asignarlo a un valor de tipo T Entonces, en el caso de una referencia remota, solo necesitamos implementar un operador de conversión implícito que lea el valor, y también hacer un operador de asignación que escriba en el valor.

 template <typename T> struct remote_ref { remote_ptr<T> ptr_; operator T() const { return rget(ptr_); } remote_ref& operator=(const T& value) { rput(ptr_, value); return *this; } }; 

Por lo tanto, podemos enriquecer nuestro puntero remoto con nuevas características potentes, en presencia de las cuales se puede desreferenciar exactamente como los punteros comunes.

 template <typename T> remote_ref<T> remote_ptr<T>::operator*() { return remote_ref<T>{*this}; } template <typename T> remote_ref<T> remote_ptr<T>::operator[](ptrdiff_t idx) { return remote_ref<T>{*this + idx}; } 

Así que ahora hemos restaurado la imagen completa que muestra cómo puede usar punteros remotos de manera normal. Podemos reescribir el sencillo programa anterior.

 void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { ptr[my_rank()] = my_rank(); } } 

Por supuesto, nuestra nueva API de puntero nos permite escribir programas más complejos, por ejemplo, una función para realizar una reducción paralela basada en un árbol [3]. Las implementaciones que utilizan nuestra clase de puntero remoto son más seguras y limpias que las que se obtienen normalmente con la API de C descrita anteriormente.

Costos que surgen en tiempo de ejecución (¡o falta de ellos!)

Sin embargo, ¿cuánto nos costaría usar una abstracción de tan alto nivel? Cada vez que accedemos a la memoria, llamamos al método de desreferenciación, devolvemos el objeto intermedio que envuelve el puntero, luego llamamos al operador de conversión o al operador de asignación que afecta al objeto intermedio. ¿Cuánto nos costará en tiempo de ejecución?

Resulta que si designa cuidadosamente el puntero y las clases de referencia, entonces no habrá sobrecarga para esta abstracción en tiempo de ejecución: los compiladores de C ++ modernos manejan estos objetos intermedios y llamadas a métodos mediante incrustación agresiva. Para evaluar cuánto nos costará tal abstracción, podemos compilar un programa de ejemplo simple y verificar cómo irá el ensamblaje para ver qué objetos y métodos existirán en tiempo de ejecución. En el ejemplo descrito aquí con la reducción basada en árbol compilada con clases de punteros y referencias remotas, los compiladores modernos reducen la reducción basada en árbol a varias remote_write remote_read y remote_write [4]. No se llaman métodos de clase, no existen objetos de referencia en tiempo de ejecución.

Interacción con bibliotecas de estructura de datos.

Los programadores experimentados de C ++ recuerdan que la biblioteca de plantillas estándar de C ++ establece que los contenedores STL deben admitir asignadores de C ++ personalizados . Los asignadores le permiten asignar memoria, y luego se puede hacer referencia a esta memoria utilizando los tipos de punteros creados por nosotros. ¿Significa esto que simplemente puede crear un "asignador remoto" y conectarlo para almacenar datos en la memoria remota utilizando contenedores STL?

Lamentablemente no. Presumiblemente, por razones de rendimiento, el estándar C ++ ya no requiere soporte para tipos de referencia personalizados, y en la mayoría de las implementaciones de la biblioteca estándar C ++ realmente no son compatibles. Entonces, por ejemplo, si usa libstdc ++ de GCC, puede recurrir a punteros personalizados, pero solo están disponibles los enlaces normales de C ++, lo que no le permite usar contenedores STL en la memoria remota. Algunas bibliotecas de plantillas de C ++ de alto nivel, por ejemplo, Agencia , que utilizan tipos de puntero personalizados y tipos de referencia, contienen sus propias implementaciones de algunas estructuras de datos de STL que realmente le permiten trabajar con tipos de referencia remotos. En este caso, el programador obtiene más libertad en un enfoque creativo para crear tipos de asignadores, punteros y enlaces, y, además, obtiene una colección de estructuras de datos que pueden usarse automáticamente con ellos.

Contexto amplio

En este artículo, hemos abordado una serie de problemas más amplios y aún no resueltos.

• Asignación de memoria . Ahora que podemos hacer referencia a objetos en la memoria remota, ¿cómo reservamos o asignamos dicha memoria remota?
• Soporte para objetos . ¿Qué pasa con el almacenamiento en la memoria remota de objetos que son de tipos más complicados que int? ¿Es posible un soporte ordenado para tipos complejos? ¿Se pueden admitir tipos simples al mismo tiempo sin desperdiciar recursos en la serialización?
• Diseño de estructuras de datos distribuidos . Ahora que tiene estas abstracciones, ¿qué estructuras de datos y aplicaciones puede construir con ellas? ¿Qué abstracciones deben usarse para la distribución de datos?

Notas

[1] En UPC, los punteros tienen una fase que determina a qué rango se dirigirá el puntero después de aumentar en uno. Debido a las fases, las matrices distribuidas pueden encapsularse en punteros, y los patrones de distribución en ellas pueden ser muy diferentes. Estas características son muy poderosas, pero pueden parecer mágicas para un usuario novato. Aunque algunos ases UPC realmente prefieren este enfoque, un enfoque orientado a objetos más razonable es escribir primero una clase de puntero remoto simple y luego asegurarse de que los datos se asignen en función de las estructuras de datos específicamente diseñadas para esto.

[2] La mayoría de las aplicaciones en HPC están escritas al estilo de SPMD , este nombre significa "un programa, datos diferentes". La API SPMD ofrece una función o variable my_rank() que le dice al proceso que ejecuta el programa un rango o ID único, en función del cual puede ramificarse desde el programa principal.

[3] Aquí hay una reducción de árbol simple escrita en el estilo SPMD usando la clase de puntero remoto. El código está adaptado en base a un programa originalmente escrito por mi colega Andrew Belt .

  template <typename T> T parallel_sum(remote_ptr<T> a, size_t len) { size_t k = len; do { k = (k + 1) / 2; if (my_rank() < k && my_rank() + k < len) { a[my_rank()] += a[my_rank() + k]; } len = k; barrier(); } while (k > 1); return a[0]; } 

[4] El resultado compilado del código anterior se puede encontrar aquí .