Benchmarking linear-algebra algorithms on CPU- and FPGA-based platforms

Moore’s law is the main driving factor behind the rapid evolution of computers that has been observed in the past 50 years. Though the law is soon ending due to heat- and sizing-related issues. One solution to continuing the evolution is utilizing alternative computer hardware, where parallel hardware is especially interesting. The Field Programmable Gate Array (FPGA) is one such piece of hardware. This study compares the runtime of two linear-algebra benchmarks executed on a traditional CPU-based platform and an FPGA-based platform respectively. The benchmarks are called cholesky and durbin respectively. The cholesky benchmark performs Cholesky decomposition and the durbin benchmark computes the solution to a Yule-Walker equation. The CPU implementations of the benchmarks were provided in the C programming language and the FPGA implementations of the benchmarks were written using OpenCL, which is a High-Level-Synthesis framework. The results highlighted a clear advantage for the CPU implementations, which had a shorter runtime than the FPGA implementations in both benchmarks for every test case. This was caused by both benchmarks containing data dependencies, which required them to be executed sequentially. Since the CPU operates at a clock frequency more than ten times higher than the FPGA’s clock frequency, it executed sequential instructions faster than the FPGA.

Moores lag är den främsta orsaken till den snabba datorutveckling som skett de senaste 50 åren. På grund av svårigheter med värme och dimensionering närmar sig dock lagen sin applicerbara gräns. En lösning för att bibehålla utvecklingen är att nyttja alternativ hårdvara och särskilt intressant är parallell hårdvara. En Field Programmable Gate Array (FPGA) är ett exempel på sådan hårdvara. Denna studie jämför körtiden mellan två prestandatest för linjär-algebra-algoritmer som utvärderades på en traditionell CPU-baserad plattform och en FPGA-baserad plattform. Prestandatesterna kallas cholesky respektive durbin. Testet cholesky utför Choleskydekomposition och testet durbin löser en Yule-Walker-ekvation. CPU-implementationerna av testen tillhandahölls i programmeringsspråket C och FPGA-implementationerna av testen skrevs i OpenCL, som är ett ramverk för högnivåsyntes. Resultaten visade en tydlig fördel för CPU-implementationerna, som har en kortare körtid än FPGA-implementationerna för alla testfall i båda prestandatest. Detta orsakades av databeroenden som existerar i båda algoritmerna, vilket påtvingade en sekventiell exekvering. Då CPU:n når en närmare tio gånger högre klockfrekvens än FPGA:n exekverar den sålunda sekventiella instruktioner snabbare än FPGA:n.