Theoretical Model of Computation and Algorithms for FPGA-Based Hardware Accelerators

被引：1

作者：

Hora, Martin ^{[1
]}

Koncicky, Vaclav ^{[2
]}

Tetek, Jakub ^{[2
]}

机构：

[1] Charles Univ Prague, Comp Sci Inst, Malostranske Nam 25, Prague 11800, Czech Republic

[2] Charles Univ Prague, Dept Appl Math, Malostranske Nam 25, Prague 11800, Czech Republic

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2019 | 2019年 / 11436卷

关键词：

D O I：

10.1007/978-3-030-14812-6_18

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

While FPGAs have been used extensively as hardware accelerators in industrial computation [20], no theoretical model of computation has been devised for the study of FPGA-based accelerators. In this paper, we present a theoretical model of computation on a system with conventional CPU and an FPGA, based on word-RAM. We show several algorithms in this model which are asymptotically faster than their word-RAM counterparts. Specifically, we show an algorithm for sorting, evaluation of associative operation and general techniques for speeding up some recursive algorithms and some dynamic programs. We also derive lower bounds on the running times needed to solve some problems.

引用

页码：295 / 312

页数：18

共 27 条

[1]

Ajtai Miklos, 1983, P 15 ANN ACM S THEOR, P1

[2]

Alam NM, 2009, THESIS CLEMSON U

[3]

[Anonymous], 1999, INTRO CIRCUIT COMPLE

[4]

[Anonymous], 2009, Introduction to Algorithms

[5]

Batcher KE., 1968, Proceedings of the Spring Joint Computer Conference, P307, DOI DOI 10.1145/1468075.1468121

[6] Accelerating compute-intensive applications with GPUs and FPGAs [J].

Che, Shuai ;

Li, Jie ;

Sheaffer, Jeremy W. ;

Skadron, Kevin ;

Lach, John .

2008 SYMPOSIUM ON APPLICATION SPECIFIC PROCESSORS, 2008, :101-+

[7]

Chodowiec P, 2003, LECT NOTES COMPUT SC, V2779, P319, DOI 10.1007/978-3-540-45238-6_26

[8]

Chrysos G., 2012, 2012 IEEE 12th International Conference on Bioinformatics & Bioengineering (BIBE 2012). Proceedings, P559, DOI 10.1109/BIBE.2012.6399733

[9]

Demaine E.D., 2002, Lecture Notes from the EEF Summer School on Massive Data Sets, P1

[10]

Grozea C, 2010, LECT NOTES COMPUT SC, V6310, P105, DOI 10.1007/978-3-642-16233-6_12

← 1 2 3 →