FPGA Based Dijkstra’s Shortest Path Algorithm

A parameterizable version of Dijkstra’s shortest path algorithm was designed in VHDL with Synopsys’ FPGA
Express design software version 3.4. The design was targeted for Altera’s FLEX10K device family with the
Quartus design software. The parameterizable features of Dijkstra’s shortest path algorithm were compiled
into a separate VHDL package which was included in the main design file. This way the design of other
versions of Dijsktra’s algorithm with different accuracy and for networks of different sizes is made
easier, since all the changes are made only in the VHDL package.

Fig. 1. The top-level block diagram of the FPGA-based Dijkstra’s shortest path algorithm. The ROM block
contains the network description and the RAM block contains the temporary results of shortest path
computation. The comparator bank selects the smallest distance from the prefetched edge lengths.

The block diagram of the FPGA-based Dijkstra’s shortest path algorithm is presented in Fig. 1. The
network structure is presented in the internal ROM block of the logic device. In the block diagram
of Fig. 1, there are six address lines. This is sufficient to represent all node-to-node links of
networks of size upto eight nodes, if the network is represented as an adjacency matrix. The
internal RAM blocks of the logic device represent the known status of nodes, the distance to this
node and the previous node. There are separate address and data lines for the ROM and RAM blocks,
which allows the parallel transfer of information to/from the memory blocks. To speed up the
computations for finding the closest node from the set of unknown nodes, all node-to-node links
whose other pair is the last known node are prefetched from ROM. Then the next known node is
computed by the parallel comparator bank.

As an example, the compiled version of Dijsktra’s algorithm for networks of maximum sixe eight nodes
fitted into an EPF10K20TC144-3 device, which has 1152 logic elements (LEs) corresponding to
approximately 20000 available gates. The design required 72 per cent of all LEs and 5 per cent of
available memory bits. Logic element requirements increase linearly, since the size of the comparator
bank grows linearly. On the other hand, memory requirements increase quadratically,since the network
description of a network of size N nodes requires NxN memory locations. If the network description
requires an external memory chip, all that is needed is to add an external data and address bus and
to change the memory handling functions to handle external memory instead of internal memory.

To compare the performance of an FPGA-based Dijsktra’s algorithm with a microprocessor-based version,
an identical algorithm was coded in C and compiled with gcc in Linux Redhat 6.2. The same network
descriptions were then tried in both the FPGA-based and software-based versions of the same algorithm.
The speedup factor in favor of the FPGA-based version depended on the number of network nodes. As
network sizes grew, the average execution time of the FPGA-based version grew only linearly, whereas
the average execution time of the microprocessor-based version displayed quadratic growth
(in Table 2). This can be attributed to the more effective FPGA-based execution in Dijkstra’s
algorithm, since multiple comparators are used in parallel.

Table 2. FPGA resources required by the implementation of Dijkstra’s shortest path algorithm and a
comparison between the execution times of FPGA-based and microprocessor-based versions of the same algorithm.

Advertisements

, , , , , , , , , , , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: