Using an FPGA to Navigate China’s Railroads

If you’re headed over to mainland China as a tourist, it’s possible to get to most of the country by rail. China is huge though, about the same size as the United States and more than twice the size of the European Union. Traveling that much area isn’t particularly easy. There are over 300 train terminals in China, and finding the quickest route somewhere is not obvious at all. This is an engineering challenge waiting to be solve, and luckily some of the students at Cornell Engineering have taken a stab at efficiently navigating China’s rail system using an FPGA.

The FPGA runs an algorithm for finding the shortest route between two points, called Dijkstra’s algorithm. With so many nodes this can get cumbersome for a computer to calculate, but the parallel processing of a dedicated FPGA speeds up the process significantly. The FPGA also includes something called a “hard processor system“, or HPS. This is not a soft-core, but dedicated computing hardware in the form of an ARM Cortex-A9. Testing showed that utilizing both the HPS and the FPGA can speed up the computation by up to ten times over a microcontroller alone.

This project goes into extreme detail on the methodology and the background of the math and coding involved, and is definitely worth a read if you’re interested in FPGAs or traveling salesman-esque problems. FPGAs aren’t the only dedicated hardware you can use to solve these kinds of problems though, if you have a big enough backpack while you’re traveling around China you could also use a different kind of computer.

Continue reading “Using an FPGA to Navigate China’s Railroads”