© The Institution of Engineering and Technology
Reconfigurable hardware has recently shown itself to be an appropriate solution to speeding up problems that are highly dependent on a particular complex or repetitive sub-algorithm. In most cases, these types of solutions lend themselves well to parallel solutions. The optimal design on field programmable gate arrays (FPGAs) for problems with algorithms or sub-algorithms that can be highly parallelised is investigated. In addition, a classification system is introduced, which categorises FPGA-based solutions into ‘instance-specific’ and ‘parameter-specific’.
References
-
-
1)
-
Rice, J.E., Muzio, J.C.: `Methods for calculating autocorrelation coefficients', Proc. 4th Int. Workshop on Boolean Problems, (IWSBP), 2000, p. 69–76.
-
2)
-
Kent, K.B., Proudfoot, R.B., Zhao, Y.: `Optimizing the edit-distance problem', Proc. 17th Int. Workshop Rapid System Prototyping (RSP), June 2006, Chania, Crete, p. 14–16.
-
3)
-
M. Rinard
.
(2001)
Analysis of multithreaded programs.
-
4)
-
Cheung, R.C.C., Brown, A., Luk, W., Cheung, P.Y.K.: `A scalable hardware architecture for prime number validation', Proc. 2004 IEEE Int. Conf. Field-Program. Technol., 2004, p. 177–184.
-
5)
-
Thornton, M., Shivakumaraiah, L.: `Computation of disjoint cube representations using a maximal binate variable heuristic', Proc. IEEE Southeastern Symp. System Theory, 2002, p. 417–421.
-
6)
-
Kent, K.B., Rice, J.E.: `Using instance-specific circuits to compute autocorrelation coefficients', Proc. 1st Northeast Workshop on Circuits and Systems (NEWCAS), 14–16 June 2003, Montreal, Canada, p. 61–64.
-
7)
-
Serra, M., Kent, K.: `Using FPGAs to solve the hamiltonian cycle problem', Proc. Int. Symp. Circuits and Systems (ISCAS'03), 25–28 May 2003, Bangkok, Thailand, IEEE Press, p. III–228–III–231.
-
8)
-
Yamaguchi, Y., Miyajima, Y., Maruyama, T., Konagaya, A.: `High speed homology search using run-time reconfiguration', Proc. Field-Programmable Logic and Applications (FPL) 2002, Springer, Lecture Notes in Computer Science, p. 281–291, (LNCS, 2438).
-
9)
-
Kent, K.B., Rice, J.E., Van Schaick, S., Evans, P.A.: `Hardware-based implementation of the common approximate substring algorithm', Proc. Euromicro Symp. Digital Syst. Design: Architectures, Methods and Tools (DSD), 2005, p. 314–320.
-
10)
-
M.G. Karpovsky
.
(1976)
Finite orthogonal series in the design of digital devices.
-
11)
-
Rudell, R.: ‘Espresso minimization tool man pages.’ http://www.fke.utm.my/downloads/espresso/espresso.1.html.
-
12)
-
M. Anderson ,
S. Amarasinghe ,
M.S. Lam
.
Data and computation transformations for multiprocessors.
ACM SIGPLAN Notices
,
8 ,
166 -
178
-
13)
-
Milder, P.A., Franchetti, F., Hoe, J.C., Puschel, M.: `FFT Compiler: from math to efficient hardware HLDVT invited short paper', Proc. IEEE Int. High Level Design Validation and Test Workshop (HLDVT), 2007, p. 137–139.
-
14)
-
Yang, S.: ‘Logic synthesis and optimization benchmarks user guide version 3.0’. Downloaded from http://www.cbl.ncsu.edu/xBed/datasets/BCSP/LogSynth91/1991-IWLSUG-Saeyang/1991-IWLSUG-Saeyang.pdf.
-
15)
-
Suchitra, S., Lim, C.S., Srikanthan, T.: `Array based architecture for EZW image encoding on FPGA using Handel-C', Conf. Record of the Thirty-Eighth Asilomar Conf. Signals, Systems and Computers, 2004, 1, p. 447–450.
-
16)
-
Galanis, M.D., Kitsos, P., Kostopoulos, G., Sklavos, N., Koufopavlou, O., Goutis, C.E.: `Comparison of the hardware architectures and FPGA implementations of stream ciphers', Proc. 11th IEEE Int. Conf. on Electronics, Circuits and Systems (ICECS), 2004, p. 571–574.
-
17)
-
Rice, J.E., Kent, K.B.: `Systolic array techniques for determining common approximate substrings', Proc. Int. Symp. Circuits and Systems (ISCAS), 2006, cdrom paper 1480.pdf.
-
18)
-
Jerraya, A.A., Yoo, S., Baghdadi, A., Lyonnard, D.: `Automatic generation of application-specific architectures for heterogeneous multiprocessor system-on-chip', Proc. 38th Conf. Design Automation (DAC'01), 2001, p. 518–523.
-
19)
-
Rudell, R.: Tutorial on espresso, 2008. http://www.fke.utm.my/downloads/espresso/espresso.5.html.
-
20)
-
U. Banerjee ,
R. Eigenmann ,
A. Nicolau ,
D. Padua
.
Automatic program parallelization.
Proc. IEEE
,
2 ,
211 -
243
-
21)
-
J. Cong ,
K. Minkovich
.
Optimality study of logic synthesis for LUT-based FPGAs.
IEEE Trans. Computer-Aided Des. Integr. Circuits Syst.
,
2 ,
230 -
239
-
22)
-
A. Jantsch ,
H. Tenhunen
.
(2003)
Networks on chip.
-
23)
-
Churchill, D., Gillard, P., Hamilton, M., Wareham, T.: `Prototyping parallel sequence edit-distance algorithms in FPGA hardware', Proc. 14th Annual Newfoundland Electrical and Computer Engineering Conference (NECEC), 2004.
-
24)
-
N. Manjikian ,
T.S. Abdelrahman
.
Fusion of loops for parallelism and locality.
IEEE Trans. Parallel Distrib. Syst.
,
2 ,
193 -
209
-
25)
-
S. Hauck ,
A. DeHon
.
(2007)
Reconfigurable computing: the theory and practice of FPGA-based computation.
-
26)
-
Saldana, M., Shannon, L., Chow, P.: `The routability of multiprocessor network topologies in FPGAs', Proc. IEEE/ACM Int. Workshop System-Level Interconnect, 2006, p. 49–56.
-
27)
-
Xilinx Inc. Xst user guide, 2008.
-
28)
-
Zhao, Y.: `Maximizing performance of configurable hardware resources', 2006, Master's, University of New Brunswick.
-
29)
-
M. Saldana ,
L. Shannon ,
J.S. Yue ,
S. Bian ,
J. Craig ,
P. Chow
.
Routability of network topologies in FPGAs.
IEEE Trans. Very Large Scale Integration (VLSI) Syst.
,
8 ,
948 -
951
-
30)
-
R.A. Wagner ,
M.J. Fischer
.
The string-to-string correction problem.
J. ACM
,
1 ,
168 -
173
-
31)
-
Cong, J., Minkovich, K.: `Optimality study of logic synthesis for LUT-based FPGAs', Proc. Fourteenth ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays (FPGA), 2006, p. 33–40.
-
32)
-
P. Panda ,
F. Catthoor ,
N.D. Dutt
.
Data and memory optimization techniques for embedded systems.
ACM Trans. Des. Autom. Electron. Syst.
,
2 ,
149 -
206
-
33)
-
Sato, T., Fukase, M.: `Reconfigurable hardware implementation of host-based IDS', Proc. 9th Asia-Pacific Conf. Commun. (APCC), 2003, 2, p. 849–853.
-
34)
-
Rice, J.E.: `Autocorrelation coefficients in the representation and classification of switching functions', 2003, PhD, University of Victoria.
-
35)
-
Puttegowda, K., Worek, W., Pappas, N., Dandapani, A., Athanas, P., Dickerman, A.: `A run-time reconfigurable system for gene-sequence searching', Proc. 16th Int. Conf. VLSI Design, 2003, p. 561.
-
36)
-
Crow, J.E., Muzio, J.C., Serra, M.: `The use of autocorrelation coefficients for variable ordering for ROBDDs', Proc. 4th Int. Workshop Appl. Reed-Muller Expansion in Circuit Design (RM99), 1999, p. 185–196.
-
37)
-
Milder, P.A., Ahmad, M., Hoe, J.C., Puschel, M.: `Fast and accurate resource estimation of automatically generated custom DFT IP cores', Proc. Fourteenth ACM/SIGDA Int. Symp. Field Programmable Gate Arrays (FPGA), 2006, p. 211–220.
-
38)
-
Ritter, J., Molitor, P.: `A partitioned wavelet-based approach for image compression using FPGAs', Proc. IEEE 2000 Custom Integrated Circuits Conf. (CICC), 2000, p. 547–550.
-
39)
-
Lipton, R.J., Lopresti, D.: `A systolic array for rapid string comparison', Proc. Chapel Hill Conf. VLSI, 1985, p. 363–376.
-
40)
-
P.R. Panda ,
N.D. Dutt ,
A. Nicolau
.
Local memory exploration and optimization in embedded systems.
IEEE Transactions on Computer-Aided Des. Integr. Circuits Syst.
,
1 ,
3 -
13
-
41)
-
R. Bryant
.
Graph-based algorithms for boolean function manipulation.
IEEE Trans. Compu.
,
8 ,
677 -
691
-
42)
-
Kent, K.B., Rice, J.E., Ronda, T., Yong, Z.: `Instance-specific versus parameter-specific circuit generation', Proc. Int. Conf. Eng. Reconfigurable Syst. Algorithms (ERSA), 2005, p. 243–246.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2008.0042
Related content
content/journals/10.1049/iet-cdt.2008.0042
pub_keyword,iet_inspecKeyword,pub_concept
6
6