Browsing by Author "Bhat Narasimha, B."

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    GRASP: A greedy reconfigurable approach for shortest path
    (2008) Prasad, G.R.; Shet, K.C.; Bhat Narasimha, B.
    This paper presents GRASP ("Greedy Reconfigurable Approach for Shortest Path"), a new shortest path algorithm using reconfigurable logic. It has time complexity O(P), where 'P' is maximum of number of edges along the shortest paths from source to other nodes. It is a modification of Bellman-Ford algorithm and is highly parallel and scalable. Unlike most other shortest path algorithms, GRASP does not need to find the minimum of nodes/adjacent nodes. Hence its FPGA implementation is faster compared to other FPGA implementations. Preliminary experimental results show that a 17-node GRASP runs about 4.7 times faster compared to parallel Bellman-Ford algorithm on Xilinx Virtex II. © Springer Science+Business Media B.V. 2008.
  • No Thumbnail Available
    Item
    NATR: A new algorithm for tracing routes
    (2008) Prasad, G.R.; Shet, K.C.; Bhat Narasimha, B.
    This paper presents NATR ("New Algorithm for Tracing Routes"), a new shortest path algorithm using reconfigurable logic and has time complexity O(L), where L is shortest path length. It uses ball and string model and is highly parallel and scalable. Unlike most other shortest path algorithms, NATR does not need to find the minimum of nodes/adjacent nodes. Hence its FPGA implementation is faster compared to other FPGA implementations. Preliminary experimental results show that a 17-node NATR runs about 6.3 times faster compared to parallel Bellman-Ford algorithm on Xilinx Virtex II. © Springer Science+Business Media B.V. 2008.