Muchas aplicaciones modernas se modelan utilizando grafos de algún tipo. Dado un grafo, la alcanzabilidad, es decir, descubrir si existe un camino entre dos nodos dados, es un problema fundamental así como uno de los pasos más importantes de muchos otros algoritmos. La acumulación rápida de grafos muy grandes (hasta decenas de millones de vértices y aristas) de una diversidad de disciplinas demanda soluciones eficientes y escalables al problema de la alcanzabilidad. La informática de propósito general ha sido utilizada con éxito en Unidades de Procesamiento Gráfico (GPUs) para paralelizar algoritmos que presentan un alto grado de regularidad. En este documento, extendemos la aplicabilidad del procesamiento de GPU a la manipulación basada en grafos, rediseñando un método simple pero eficiente de etiquetado de grafos de última generación, a saber, el algoritmo GRAIL (Indexación de Alcanzabilidad de Grafos a través de Intervalos Aleatorios), a GPUs basadas en CUDA de muchos núcleos. Este algoritmo genera primero una etiqueta para cada vértice del grafo, luego explota estas etiquetas para responder a consultas de alcanzabilidad. Desafortunadamente, el algoritmo original ejecuta una secuencia de visitas en profundidad que son intrínsecamente recursivas y no se pueden implementar eficientemente en sistemas paralelos. Por esa razón, diseñamos un enfoque alternativo en el que una secuencia de visitas en anchura sustituye a la búsqueda original en profundidad para generar el etiquetado, y en el que se explota un alto número de visitas concurrentes durante la evaluación de la consulta. El documento describe nuestra estrategia para rediseñar estos pasos, las dificultades que encontramos para implementarlos y las soluciones adoptadas para superar las principales ineficiencias. Para demostrar la validez de nuestro enfoque, comparamos (en términos de tiempo y requisitos de memoria) nuestro enfoque basado en GPU con la herramienta original secuencial basada en CPU. Finalmente, informamos algunas pistas sobre cómo llevar a cabo investigaciones adicionales en el área.