FPGA Acceleration of Semantic Tree Reasoning Algorithms
J. Barba; M.J. Santofimia; D. Fuente de San Venancio; J.D. Dondo; F. Rincón; J. Caba
Cenference: Jornadas de Computación Reconfigurable y Aplicaciones
Location: Madrid (España)
Date: 17/09/2013 - 20/09/2013
Pages: 81-88
ISBN: 978-84-695-8318-0
Data structures, and the algorithms to handle them, represent the foundation of many software applications. Normally, its implementation involves the use of dynamic references (pointers) to memory regions in which part of the information is stored. Such dynamic artifacts, present in the software domain, do not suit quite straight in the hardware domain if a silicon realization of these dynamic data structures is planned. Therefore, many application domains cannot benefit from the use of specialized hardware implementing data structures such as lists, graphs or trees. In this paper, the design of a hardware unit to accelerate semantic tree operations for common-sense reasoning applications is presented. The optimized micro-architecture together with a smart data mapping strategy allows our solution to achieve a significant reduction in execution times of marker-parser algorithms. The design has been prototyped on a Xilinx ML507 board and compared to an equivalent software implementation.