Paralarpd: enrutador FPGA paralelo utilizando el método de subgradiente primal-dual
Autores: Agrawal, Rohit; Ahuja, Kapil; Hau Hoo, Chin; Duy Anh Nguyen, Tuan; Kumar, Akash
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Paralarpd: enrutador FPGA paralelo utilizando el método de subgradiente primal-dual
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Campo de matrices programables
Enrutamiento
Programación lineal
ParaLaR
Violación de restricciones
Métrica estándar
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
En el flujo de diseño de arrays de compuertas programables en campo (FPGA), uno de los pasos más demorados es el enrutamiento de redes. Por lo tanto, hay una necesidad de acelerarlo. En un trabajo reciente de Hoo et al., los autores han desarrollado un marco basado en programación lineal (LP) que paraleliza este proceso de enrutamiento para lograr mejoras significativas en la velocidad (el algoritmo resultante se denomina ParaLaR). Sin embargo, este enfoque tiene ciertas debilidades. Específicamente, la violación de las restricciones por la solución y una métrica de enrutamiento estándar podrían mejorarse. Abordamos estos dos problemas aquí. En este documento, utilizamos el marco LP de ParaLaR y lo resolvemos utilizando el método de subgradiente primal-dual que explota mejor las propiedades del problema. También proponemos una mejor manera de actualizar el tamaño del paso tomado por este algoritmo iterativo. Llamamos a nuestro algoritmo ParaLarPD. Realizamos experimentos en un conjunto de benchmarks estándar, donde mostramos que nuestro algoritmo supera no solo a ParaLaR, sino también al algoritmo existente estándar VPR. Realizamos experimentos con dos configuraciones diferentes. Logramos una mejora promedio en la violación de las restricciones y en la métrica estándar del ancho mínimo del canal (ambos relacionados) en comparación con ParaLaR. En comparación con VPR, obtenemos mejoras promedio en el ancho mínimo del canal (no hay violación de restricciones en VPR). Obtenemos el mismo valor para la longitud total del cable que ParaLaR, que es mejor en promedio que el obtenido por VPR. Esta es la métrica original a minimizar, para la cual se propuso ParaLaR. A continuación, examinamos la tercera métrica fácilmente mensurable del retardo de la ruta crítica. En promedio, ParaLarPD da un retardo de ruta crítica mayor que ParaLaR y mejor que VPR. Logramos mejoras máximas en la velocidad relativa de hasta siete veces al ejecutar una versión paralela de nuestro algoritmo utilizando ocho hilos en comparación con la implementación secuencial. Estas mejoras en la velocidad son similares a las obtenidas por ParaLaR.
Descripción
En el flujo de diseño de arrays de compuertas programables en campo (FPGA), uno de los pasos más demorados es el enrutamiento de redes. Por lo tanto, hay una necesidad de acelerarlo. En un trabajo reciente de Hoo et al., los autores han desarrollado un marco basado en programación lineal (LP) que paraleliza este proceso de enrutamiento para lograr mejoras significativas en la velocidad (el algoritmo resultante se denomina ParaLaR). Sin embargo, este enfoque tiene ciertas debilidades. Específicamente, la violación de las restricciones por la solución y una métrica de enrutamiento estándar podrían mejorarse. Abordamos estos dos problemas aquí. En este documento, utilizamos el marco LP de ParaLaR y lo resolvemos utilizando el método de subgradiente primal-dual que explota mejor las propiedades del problema. También proponemos una mejor manera de actualizar el tamaño del paso tomado por este algoritmo iterativo. Llamamos a nuestro algoritmo ParaLarPD. Realizamos experimentos en un conjunto de benchmarks estándar, donde mostramos que nuestro algoritmo supera no solo a ParaLaR, sino también al algoritmo existente estándar VPR. Realizamos experimentos con dos configuraciones diferentes. Logramos una mejora promedio en la violación de las restricciones y en la métrica estándar del ancho mínimo del canal (ambos relacionados) en comparación con ParaLaR. En comparación con VPR, obtenemos mejoras promedio en el ancho mínimo del canal (no hay violación de restricciones en VPR). Obtenemos el mismo valor para la longitud total del cable que ParaLaR, que es mejor en promedio que el obtenido por VPR. Esta es la métrica original a minimizar, para la cual se propuso ParaLaR. A continuación, examinamos la tercera métrica fácilmente mensurable del retardo de la ruta crítica. En promedio, ParaLarPD da un retardo de ruta crítica mayor que ParaLaR y mejor que VPR. Logramos mejoras máximas en la velocidad relativa de hasta siete veces al ejecutar una versión paralela de nuestro algoritmo utilizando ocho hilos en comparación con la implementación secuencial. Estas mejoras en la velocidad son similares a las obtenidas por ParaLaR.