Although some interesting routing algorithms based on HNN were already proposed, they are slower when compared to other routing algorithms. Since HNN are inherently parallel, they are suitable for parallel implementations on parallel platforms, such as Field Programmable Gate Arrays (FPGA) and Graphic Processing Units (GPU). In this chapter, the authors show parallel implementations of a routing algorithm based on Hopfield Neural Networks (HNN) for GPU and for FPGAs, considering some implementation issues. They analyze the hardware limitation on the devices, the memory bottlenecks, the complexity of the HNN, and, in the case of GPU implementation, how the kernel functions should be implemented, as well as, in the case of the FPGA implementation, the accuracy of the number representation and memory storage on the device. The authors perform simulations for one variation of the routing algorithm for three communication network topologies with increasing number of nodes. They achieved speed-ups up to 78 when compared the FPGA model simulated to the CPU sequential version and the GPU version is 55 times faster than the sequential one. These new results suggest that it is possible to use the HNN to implement routers for real networks, including optical networks.
TopIntroduction
Routing algorithms have been intensively discussed in the scientific community, mainly because the routing process impacts drastically on the performance of communication networks. An ideal routing algorithm comprises finding the best path between the source and the destination nodes, enabling high quality transmission, avoiding penalties caused by physical layer impairments and reserving resources for future requests. There are different ways to determine a route. Some algorithms determine the routes based on the shortest path (SP) (Dijkstra, 1959), the minor delay (Ali & Kamoun, 1993), the higher Signal to Noise Ratio (Pereira, Chaves, Bastos-Filho, & Martins-Filho, 2008), the better load distribution (N. Kojic, Reljin, & Reljin, 2004), among others.
Computational Intelligence is a set of techniques with an ability to learn and to deal with new situations (Engelbrecht, 2007). Among these techniques, Neural Networks are inspired by the brain and by the biological neurons. They have the ability of learning and decision-making.
Hopfield Neural Network (HNN) is a class of Neural Networks with feedback that may be used for routing computer networks (Hopfield, 1982). Once they are adaptive, they are an interesting option to be used as routing algorithm in order to handle the dynamic behavior presented in computer networks. Moreover, it is also possible to be used in optical networks (N. Kojic, Reljin, & Reljin, 2004; N. S. Kojic, Reljin, & Reljin, 2006, 2007, 2009; Bastos-Filho, Santana, Silva, Martins-Filho, & Chaves, 2010).
However, although they work well to solve the routing problem, they are still slower than the other approaches used nowadays (Dijkstra, 1959). On the other hand, the neural networks are inherently parallel, once the neurons perform their operations individually. Therefore, they are suitable to be implemented on parallel platforms in order to improve their performance.
In the recent years, the use of Graphic Processing Units (GPUs) has been proposed for many scientific applications (Bastos-Filho, Oliveira Junior, Silva & Santana, 2011). The GPU parallel floating point processing capacity allows one to obtain high speed-ups. Nevertheless, there are some aspects that should be considered to adapt an application to run on these platforms, such as memory allocation and communication between blocks. Furthermore, hardware limitations of the GPUs bound the use of this technology for general purposes.
Field Programmable Gate Arrays (FPGA) are programmable logic devices organized in a bi-dimensional matrix of logic cells (Pedroni, 2004). The architecture presented in the FPGAs allows them to process data in parallel manner, thus they may be used to implement parallel algorithms.
Therefore, due to the parallel behavior of the neural networks and the parallel architecture of the FPGA and the GPUs, it is possible to have an routing algorithm based on Hopfield Networks running on these parallel platforms and have a similar performance to the standard algorithms used nowadays (Bastos-Filho, Oliveira Junior, Silva & Santana, 2011; Oliveira Junior & Bastos-Filho, 2011).
Furthermore, the adaptive capability of the neural networks may be used in real networks. In this chapter, we propose a Hopfield Neural Networks model for FPGA. We validate the model and show that it is possible to have the routing algorithm running on FPGAs. Moreover, we also show that the approximation on the activation function does not harm the model performance mitigation. Since Bastos-Filho (2011) demonstrated that it is possible to use HNN for routing in optical networks, we believe that one can extend the results presented in this paper to optical networks in order to develop a fast router for these networks.