Arg - max 77

+

OpenCL ™ Optimización Estudio de caso: Formación de Apoyo Vector Machine por Bryan Catanzaro, 2/11/2011 En este artículo, examinamos los núcleos claves utilizadas en un solucionador de programación cuadrática para la formación de la máquina de vectores de soporte. Optimizamos la evaluación de la Función de base radial núcleo SVM mediante el examen de una variedad de diferentes estructuras de datos, así como sus consecuencias en el rendimiento, mejorando el rendimiento en un factor de 5 en comparación con el código ingenua que se ejecuta en un procesador AMD Radeon ™ HD 5870 GPU. We discutir en general reglas generales que conducen a estructuras de datos eficientes para la computación OpenCL ™. Introducción Support Vector Machines (SVMs) son una técnica de clasificación binaria ampliamente utilizada utilizado para analizar los datos, o en otras palabras, para etiquetar los datos como pertenecientes a una de dos categorías. Por ejemplo, las SVM se pueden utilizar para determinar si el correo electrónico es importante o no solicitada, si una imagen contiene una flor o no, o si una secuencia de ADN codifica un rasgo particular, etc. Los investigadores en muchos campos, como la imagen, la palabra y el gesto el reconocimiento, la bioinformática y la seguridad informática han aplicado las SVM para permitir que los programas para analizar los datos. Para utilizar una SVM, primero debe ser entrenado, por lo que el clasificador puede "aprender" las categorías que distingue entre. Este proceso de formación es computacionalmente intensivas. En este artículo, vamos a discutir los problemas que surgen cuando se construye un solver iterativo para la formación de la máquina de vectores de soporte, que se ejecuta en las GPU de AMD, utilizando OpenCL. Most del artículo se centrará en el uso adecuado de la memoria en el chip y fuera de chip los recursos de las estructuras de datos GPU. The AMD Radeon HD 5870 que elegimos determinar la eficiencia con que podemos utilizar nuestros recursos de memoria, por lo que este artículo se examinan varias formas de dejar fuera las estructuras de datos y su uso en el código OpenCL, con el fin de lograr un buen rendimiento. Máquina de vectores de soporte Formación Para empezar esta discusión, en primer lugar vamos a describir brevemente el problema que estamos tratando de solve. As anteriormente mencionados, las SVM son una clasificación ampliamente utilizado datos de proceso technique. Support máquinas de vectores como puntos en alguna característica del espacio abstracto, altamente dimensional. Por ejemplo, podría describir objetos mediante la medición de sus dimensiones exteriores (longitud, anchura, altura), así como su masa. Cada objeto sería entonces ser descrita por cuatro números, que podemos pensar como un vector de cuatro dimensiones en un espacio de características. SVM aplicaciones típicas utilizan espacios de características con decenas a cientos de dimensiones, o en ocasiones más. Teniendo en cuenta una serie de medidas de objetos, junto con sus etiquetas asociadas, podría entonces formar una SVM para distinguir entre dos clases diferentes de objetos, por ejemplo: entre los objetos hechos de madera, y los de los objetos de madera stone. Since tendería a residir en una cierta región del espacio de características mi hijo de cuatro dimensiones, y objetos de piedra tendería a residir en otra región, podemos trazar un límite en nuestro espacio de características que separa los objetos de madera a partir de los objetos de piedra. Por supuesto, hay muchos de esos límites que podríamos dibujar, pero que quieren aprender el límite más general que podamos, para que nuestro clasificador será robusto. El entrenamiento de un SVM es un enfoque específico para el aprendizaje de la frontera que separa los datos de entrenamiento con un margen máximo, lo que significa que los datos de entrenamiento se clasifica claramente como sea posible. A continuación, un programa puede clasificar nuevos datos simplemente comprobando para ver de qué lado de la frontera los nuevos datos cae en. SVM pueden ser entrenados utilizando un proceso de optimización de programación cuadrática secuencial denominado mínimo de optimización. En este algoritmo, tomamos muchos pequeños pasos para actualizar el límite entre nuestros dos classes. This de objeto se hace mediante la búsqueda de los dos puntos de entrenamiento que se explican más mal por nuestra suposición actual de lo que es el límite, y luego actualizar el límite para encajar a esos puntos mejor. Figura 1: Un límite que separa las imágenes de plantas a partir de imágenes de personas La principal carga de cálculo en este algoritmo es la elección de los dos puntos más mal explicada fuera de nuestro conjunto de entrenamiento, que puede ser de cientos de miles de puntos en total. Se trata de evaluar una función de la distancia entre todos los puntos de entrenamiento y dos de los puntos de entrenamiento. Esta función de distancia, llamada una función kernel, puede tomar muchas formas, pero uno de los más útiles es la denominada función de base radial. Nuestro trabajo es, pues, para evaluar muchas copias de esta función, por nuestros muchos puntos de entrenamiento. Análisis inicial Veamos una versión simple de la C Radial evaluations. We're Función de base va a evaluar todos los puntos de datos contra dos de los puntos de datos, uno llamado alto y el otro se llama baja. Almacenaremos los resultados de dos matrices, una denominada high_kernel y el otro llamado low_kernel. Tenemos NPOINTS puntos de entrenamiento, cada una de las cuales es una muestra de una función unidimensional Ndim space. We'll almacenar los puntos de datos en una matriz de datos llamada. donde cada fila representa un punto de entrenamiento, por lo que la matriz resultante tiene NPOINTS filas y columnas Ndim. Por ahora, vamos a almacenar la matriz mediante el diseño de datos "por filas" C estándar, del que hablaremos con más detalle más adelante en el artículo. gamma es el parámetro escalar de nuestra función de base radial. Listado 1 muestra algunos simple código C para lograr esto. Listado 1: Código de C simple para RBF núcleo evaluaciones En este código, hemos fusionado tanto las evaluaciones de alta y baja del núcleo juntos en un bucle interior, con el fin de evitar la sobrecarga de la carga del vector dos veces para cada iteración del bucle exterior. Podemos ver la disposición de los datos por filas en la aritmética de indexación en el bucle interno: para cargar datos o datos de manera equivalente en el Listado 1, que en el índice de datos, donde Ndim es el número de columnas en cada fila. Discutiremos esto en detalle más adelante. También podemos ver que en el bucle interior, hay 6 operaciones de punto flotante y tres cargas de memoria. Sin embargo, ya que los vectores de alta y baja son los mismos para cada iteración del bucle exterior, si escribimos nuestro código correctamente, vamos a sólo tenemos que cargarlos una vez en recuerdos en el chip, y luego vamos a reutilizar sin tener para ejecutar una carga de memoria fuera del chip en el bucle interno. El código del Listado 1 no hace esto, es un ejemplo de una implementación simple C sin ninguna optimización. Más adelante, veremos cómo implementar esta optimización para evitar el desperdicio de ancho de banda de memoria. Podemos utilizar esta información para calcular una cota en nuestro rendimiento esperado de este código, se ejecuta en el procesador AMD Radeon HD 5870. La Radeon HD 5870 tiene 153,6 GB / s de ancho de banda de memoria fuera del chip. Suponiendo perfecta de almacenamiento en caché de las altas y bajas vectores, deberíamos ver 153,6 GB / segundo * 6 Operaciones de precisión de un solo punto flotante de carga de carga * 1 Memoria / Memoria / 4 bytes = 230,4 precisión simple operaciones de punto flotante / segundo. Vamos a utilizar esta obligado a evaluar la calidad de nuestras implementaciones como optimizamos. Implementación básica OpenCL Traducir el código C directamente a OpenCL, vamos a crear una instancia de un elemento de trabajo para cada iteración del bucle más externo. El Listado 2 muestra una traslación directa de OpenCL nuestra sencilla aplicación C del Listado 1. Listado 2: Traducción directa del código OpenCL C simple para la evaluación del kernel RBF Al comparar el Listado 2 para el Listado 1, podemos ver que hemos tomado el bucle más externo y lo convirtió en un núcleo de OpenCL, donde el espacio de índice del núcleo OpenCL corresponde a las iteraciones del bucle más externo. Actuación Figura 2: Rendimiento Fila Mayor RBF Evaluación del núcleo La Figura 2 muestra el rendimiento que logramos con esta aplicación, con los datos de dimensionalidad 1000. Para los problemas más grandes, alcanzamos 34 Giga precisión simple de punto flotante de Operaciones / segundo (SPGFLOP / s). Por desgracia, esto es sólo el 15% de nuestro límite. Claramente, hay algunas cosas que debemos investigar para mejorar el rendimiento. Por filas frente a la columna-principal Puesto que estamos claramente un cuello de botella de rendimiento de la memoria, debemos examinar nuestra elección de estructuras de datos. Más temprano, decidimos mantener nuestra matriz de datos de entrenamiento en el diseño layout. Row-major fila-principal defecto C representa una matriz de dos dimensiones como una matriz unidimensional en los escaneos a través de las filas, así: Figura 3: Fila Mayor diseño, color indica esquema de acceso Vamos a imaginar cómo esta estructura de datos se está utilizando en nuestro program. We're crear instancias de un elemento de trabajo para cada fila de la matriz, y cada elemento de trabajo, a continuación, iterar a través de las columnas de la matriz. Tenga en cuenta la primera iteración del bucle más interior de la matriz de ejemplo que se ilustra en la Figura 3: trabajo a punto 0 se carga el elemento 0 de la matriz de datos, y el trabajo con el tema 1 se carga el elemento 3 de la matriz de datos. Durante la siguiente iteración, el trabajo a punto 0 se carga el elemento 1, y el trabajo con el tema 1 se carga el elemento 4, etc. Este patrón es un código de color en la figura 3. Con esta disposición de los datos de acuerdo al avance de cálculo, los elementos de trabajo no serán accediendo lugares contiguos en la memoria fuera del chip. Esto hace que las ineficiencias, ya que los subsistemas de memoria de todos los procesadores modernos están optimizados para la carga de vectores contiguas de la memoria fuera del chip. Podemos cambiar este comportamiento mediante la reestructuración de nuestros datos, en este caso pasar de un diseño "por filas" a un diseño de "columna-principal". diseño de columna-principal representa una matriz de dos dimensiones como una matriz unidimensional en los escaneos a través de las columnas, así: Figura 4: Columna Mayor diseño, color indica esquema de acceso Con diseño de columna-principal, adyacentes elementos de trabajo tendrán acceso a los elementos adyacentes en la memoria como el producto de cálculo, como se muestra en la Figura 4. Esto mejora la eficiencia. Se trata de un simple cambio en nuestro código OpenCL. Para una matriz con los elementos Ndim en cada fila y NPOINTS filas, con el fin de los datos de índice de elemento cambiamos de la indexación por filas: los datos a la columna principal indexación. También vamos a hacer una optimización adicional mediante el relleno de los datos para asegurar que nuestras cargas siempre están alineados (ver el OpenCL Optimización Estudio de caso: artículo Diagonal de matrices dispersas vector de multiplicación para más detalles). Esto cambiará nuestra aritmética de indexación a lo siguiente: datos se encuentra por la indexación de datos. donde de paso es NPOINTS redondea al múltiplo más cercano de 32 carrozas, que es la inclinación de alineamiento preferido para la Radeon de AMD 5870 GPU. We'll también simplificar el cálculo de indexación a zancadas directamente a través de la memoria, más que vuelve a calcular el índice de nuevo cada iteración. Este código se muestra en el Listado 3. Listado 3: Columna-principal de almacenamiento de datos Al comparar el código en el Listado 3 al código en el Listado 2, podemos ver que el único cambio que hemos hecho es en la forma en que ha accedido a la structures. Instead datos de zancadas por 1 elemento de ciclo que recorre las dimensiones de los datos, que ahora paso por el simple cambio de tono elements. This tiene un gran impacto en el rendimiento. Figura 5: Columna-mayor rendimiento La figura 5 muestra la mejora del rendimiento que vemos cuando se mueve a un diseño de datos de la columna-principal. Para tamaños más grandes problemas, el rendimiento promedio sube 33,7-65,7 SPFLOP / s, que es casi un factor de 2 mejora. En comparación con nuestro rendimiento unido, vemos que hemos logrado el 29% de nuestros bound. Perhaps allí todavía hay margen de mejora. vectorización GPU de AMD (CPU y, para el caso) son más eficientes cuando cada elemento de trabajo-opera sobre los vectores de datos, en lugar de sólo escalares. Podemos vectorizar el bucle mediante la realización de esta transformación. El Listado 4 muestra cómo lograr esto. Listado 4: Cálculo vectorizada En el Listado 4, hemos cambiado el cálculo de manera que cada elemento de trabajo-trabaja en 4 elementos de datos a la vez. Utilizamos las cargas de vectores y tiendas de la memoria, a través de la intrínseca vload4 proporcionada por OpenCLWe también el uso de puntos de OpenCL intrínseca para ejecutar una operación de suma horizontal a través del vector en cada-elemento de trabajo. Actuación Figura 6: Rendimiento vectorizada Esta transformación mejora el rendimiento promedio en un 30%, a 85,9 SPGFLOP / s, que es el 37% de nuestro límite. Ahora que hemos mejorado la eficiencia de la ejecución por vectorización, tal vez deberíamos volver a nuestro tráfico memoria para reducir las cargas de memoria fuera del chip. El uso de OpenCL Imágenes imágenes OpenCL permiten el uso de memorias en el chip de sólo lectura data. Since los dos vectores que son compartidos por todos los elementos de trabajo son, de hecho, los datos de sólo lectura, tal vez tenga sentido utilizar las instalaciones de imagen de OpenCL para usar la GPU en - chip memories. To hacer esto, representamos cada vector como una imagen de dos dimensiones, donde cada píxel tiene cuatro valores de coma flotante, y sólo hay una fila de píxeles de la imagen. En el código OpenCL, los vectores de alta y baja están ahora representados por los tipos image2d_t, que encapsulan las referencias a las altas y bajas vectores, en lugar de índices en la matriz de datos. Para inicializar el muestreador imagen apropiada para esta aplicación, observamos que no queremos utilizar una imagen de punto flotante de direccionamiento (CLK_NORMALIZED_COORDS_FALSE), queremos sujetar los accesos a la imagen a los límites de la imagen (CLK_ADDRESS_CLAMP), y queremos agarrar el píxel más cercano a las coordenadas que especificamos (CLK_FILTER_NEAREST). Lee partir de los vectores de alta y baja se realizan a continuación, a través de read_imagef () calls. Listing 5 muestra el aspecto que tiene. El Listado 5: El uso de imágenes de OpenCL para cargar los datos El Listado 5 utiliza imágenes de OpenCL para todas las cargas a los vectores de alta y baja reutilizar en gran medida. Sin embargo, el uso de imágenes tiene un precio: los datos deben ser colocados en las imágenes de forma explícita, y el costo para hacer esto es mucho más alta que la escritura con el estándar OpenCL buffers. We discutir los medios eficientes para la solución de este problema en la próxima sección. La escritura en Imágenes En nuestra aplicación, los vectores de alta y baja cambian cada iteración, lo que significa que tenemos que actualizar las imágenes que los contienen. Hay una llamada API OpenCL que puede copiar una memoria intermedia de OpenCL, que ya residen en el dispositivo, a una OpenCL imagen en el dispositivo: clEnqueueCopyBufferToImage. Sin embargo, esta función no hace más trabajo de lo que sea estrictamente necesario para nuestros propósitos, y por lo tanto incurre en gastos generales muy grande. Ya que estamos llamar a esta función miles de veces en un bucle de optimización, hay que evitar incurrir en tales gastos generales, o de lo contrario nuestra aplicación general a correr lentamente, independientemente de lo bien que hemos optimizado los granos. En lugar de utilizar clEnqueueCopyBufferToImage, podemos escribir nuestra propia rutina que realiza la misma funcionalidad, ya que las imágenes en OpenCL se pueden escribir directamente. Mostramos esta rutina en el Listado 6. Listado 6: Rutina copiar de OpenCL OpenCL Los tampones de Imágenes Al invocar este núcleo para copiar los vectores de alta y baja correctos en OpenCL Imágenes de cada iteración, incurrimos en alguna sobrecarga, pero alrededor de 100 veces menos sobrecarga que incurra el uso de llamada a la API OpenCL directos. A continuación, vamos a ver el rendimiento con y sin esta sobrecarga. Actuación Figura 7: RBF kernel rendimiento utilizando Imágenes En cuanto a la computación solo, el uso de imágenes mejora nuestro rendimiento en un 75%, a 150,9 SPGFLOP / s para grandes problemas. Sin embargo, para usar prácticamente imágenes en esta solicitud, tenemos que incluir la sobrecarga adicional de la inicialización de las imágenes en cada iteración, que reduce el rendimiento de 115,6 SPGFLOP / s, en promedio. Sin embargo, esto es un 35% mejor que nuestro código vectorizado sin imágenes, y nos lleva al 50% de nuestro rendimiento ligado. memoria local En esta aplicación, sabemos exactamente lo que va a ser compartida entre los elementos de trabajo de datos. Además, el tamaño de los datos es limitada - ya que la mayoría tienen problemas SVM característica dimensionalidad espacial que es sólo en los cientos de miles de baja, deacuerdo a los vectores de alta y baja en la memoria local directamente en el chip. En el Listado 7, asignamos espacio en la memoria local para contener vectores de características de hasta 1.000 dimensiones. Listado 7: Uso de la memoria local para almacenar los datos reutilizados Este código es muy similar al código en el Listado 4, con la excepción de que copiamos manualmente sobre los vectores de entrada en OpenCL memoria local antes de proceeding. It importante sincronizar después de que termine de cargar los datos en la memoria local, para asegurar que todo trabajo artículos terminar de cargar sus datos, y que todas las cargas a la memoria local son visibles para todos los elementos de trabajo en el grupo de trabajo. Una vez que hemos hecho esto, el resto de la computación puede continuar usando la memoria sólo en el chip para las altas y bajas vectores. Actuación Figura 8: RBF kernel de rendimiento utilizando la memoria local Rendimiento utilizando la memoria local todavía se mejora aún más, en un 50% en comparación con el uso de nuestra solución de archivo. En promedio grandes problemas, alcanzamos 173,6 SPGFLOP / s, que es el 75% de nuestro desempeño bound. Although mejora adicional es probable que todavía sea posible, sabemos que va a producir rendimientos decrecientes en comparación con nuestra aplicación, ya que hemos conseguido bastante cerca de nuestra rendimiento ligado. Arg arg min Reducción máx Con el fin de implementar el algoritmo SMO, también necesitamos un arg arg min y max reduction. The arg min reducción Busca el índice del elemento más pequeño de una matriz, junto con el propio elemento, y la reducción arg max es la misma, excepto se encuentra el elemento más grande en un ejemplo array. For, una reducción en la matriz min (4.0, 2.0, 5.0, 6.0) devolvería el valor "2.0", pero una reducción min arg en la misma matriz se devolverá el valor "2.0 ", en la posición de índice" 1 ". Para aplicar estas reducciones de manera eficiente, las estrategias que describen nuestro artículo sobre aplican reducciones simples. Hay dos cosas adicionales que deben hacerse para obtener un buen rendimiento. En primer lugar, utilice la "Estructura de matrices" formato para representar la matriz y sus acompañantes indices. In otras palabras, en lugar de construir una matriz unificada de valor (índice), parejas (la "matriz de estructuras" formato), crear dos matrices independientes , uno para los índices, y una para los values. This simplifica la indexación de memoria y, en general mejora la eficiencia. En segundo lugar, con el fin de evitar la introducción de flujo de control extraños en el árbol de reducción, lo que puede reducir el rendimiento, es mejor utilizar la instrucción de selección OpenCL para realizar las operaciones arg arg min y max. Por ejemplo, el siguiente fragmento de código utiliza el operador ternario C. para realizar una operación arg min en un vector float4. int4 a_idx, b_idx; int4 less_than = is_less (a, b); min = float4 less_than. a. segundo; int4 min_idx = less_than. a_idx. b_idx; Este código es funcionalmente correcto, pero es más difícil compilar, y por lo tanto puede reducir el rendimiento. En lugar de utilizar el flujo de control, se puede utilizar el OpenCL seleccionar intrínseca, lo que da un rendimiento óptimo int4 a_idx, b_idx; int4 less_than = is_less (a, b); float4 min = seleccione (b, a, less_than); int4 min_idx = seleccionar (b_idx, a_idx, less_than); Siguiendo estas directrices, se reduzca min arg que realiza esencialmente idéntica a la reducción más simple min. En nuestra aplicación, necesitamos llevar a cabo tanto un arg min y una operación arg max a través de la vector. We investigados mejorar el rendimiento mediante la fusión de ambas reducciones en un único núcleo de OpenCL, pero se encontró que la mayor complejidad de un núcleo tales eran mayores que los beneficios de rendimiento. En concreto, la fusión de la dos reducciones juntos un rendimiento reducido en un 13%, en comparación con el uso de dos reducciones separadas. Figura 9: Min frente Arg min frente al rendimiento de reducción Fundida Arg Extrema Como se muestra en la Figura 9, la fusión de ambas las reducciones arg min y arg max en una sola reducción fue contraproducente. La aplicación fue significativamente más complejo, y el rendimiento fue ligeramente peor que acaba de realizar dos reducciones más simples. El ancho de banda limitado obligado en este cálculo es de 39,4 GigaReductions / segundo, ya que el dispositivo tiene 157,6 GB / s, y cada elemento del vector se reduce es de 4 bytes, el más rápido que podíamos ir es 157,6 / 4 = 39,4 GigaReduction / segundo. Para los grandes problemas de tamaño, que estamos realizando 33,4 GigaReductions / segundo, que es el 84% de nuestro ancho de banda limitado obligado, y nos dice que estamos cerca de óptima. Conclusión En este artículo, hemos discutido las estrategias de implementación de las partes principales de cómputo de la formación SVM. Como suele ser el caso en OpenCL optimización, conseguir un buen rendimiento requiere una cuidadosa atención al subsistema de memoria. En particular, se encontró que garantizar la memoria fuera del chip contiguo accede mediante la elección del diseño de datos de columna-principal rindió importantes ventajas de rendimiento, y haciendo uso de los recursos de memoria en el chip también fue crucial para el rendimiento. Siguiendo estas directrices, llevamos a nuestra rutina de evaluación RBF núcleo inicial a partir de 34 a 174 SPGFLOP / s, con un 75% de la teórica performance. We limitada de memoria también mostró cómo hacer las rutinas de reducción más complicados necesarios para la formación SVM un buen desempeño. Al optimizar sus propios cálculos OpenCL, recuerde estas estrategias: Tratar de averiguar cuáles son los límites de rendimiento de la aplicación están en el hardware que se está dirigiendo. De esa manera usted será capaz de saber lo bien que potencialmente podría conseguir límites de ancho de banda. Memory menudo son fáciles de obtener y por lo que son un buen punto de partida, aunque otras restricciones también pueden ser importantes. Reorganizar sus estructuras de datos de manera que elementos de trabajo adyacentes acceso palabras adyacentes en la memoria, si es posible. Para algunas cargas de trabajo esto es más fácil que otros, pero puede ser una optimización muy importante. Durante dos estructuras de datos dimensionales, pensar acerca de si una disposición por filas o de las columnas importante sería más eficiente para su problema. Utilizar memorias en el chip manera más eficaz posible. La memoria local es generalmente el más rápido, pero ya que tienes a buscar explícitamente los datos en la memoria local, puede ser más difícil de usar que las imágenes. Utilice Estructura del formato de matrices en lugar de la matriz de formato de estructuras, como una regla general. programación OpenCL puede ser muy emocionantes - pequeños cambios en su código puede llevar a grandes ganancias de rendimiento, lo que significa que un poco de pensamiento acerca de cómo su código se ejecutará en OpenCL puede dar lugar a grandes beneficios de rendimiento. OpenCL y el logotipo abierto CL son marcas comerciales de Apple Inc. utilizadas por el permiso de Khronos.