Parallel FPGA implementation of DCD algorithm

TY - GEN

T1 - Parallel FPGA implementation of DCD algorithm

AU - Liu, Jie

AU - Quan, Zhi

AU - Zakharov, Yuriy

PY - 2007

Y1 - 2007

N2 - Parallel implementation of the dichotomous coordinate descent (DCD) algorithm is proposed and analyzed. The DCD algorithm allows, multiplication-free Solution of the normal equations. The computational load of the algorithm is mainly due to "successful" iterations, when an N-length auxiliary vector is updated, N being the problem size. The parallel design exploits the fact that element of the auxiliary vector call he updated simultaneously. As such an Update involves additions and bit-shifts only, the increase in complexity compared with the serial implementation is not significant, while the throughput call be enhanced. Two parallel designs are proposed; the first uses registers for the system matrix, while the second uses random access memory (RAM). The use of RAM significantly reduces the chip area (number of FPGA slices) without decreasing the throughput. The RAM design exploits the fact that, for the update of the auxiliary vector, only one row of the system matrix is used. The proposed parallel design is verified by applying to an MVDR antenna array beamformer. It is also compared with a QRD-based MVDR beamformer exploiting CORDIC processors. Antenna beampattern obtained from weights calculated in the fixed-point FPGA implementation is compared with a floating-point simulation. The comparison shows good match for a 9-element linear array. The proposed design call provide weight update rate as high as 27 kHz for a 9-element MVDR beamformer.

AB - Parallel implementation of the dichotomous coordinate descent (DCD) algorithm is proposed and analyzed. The DCD algorithm allows, multiplication-free Solution of the normal equations. The computational load of the algorithm is mainly due to "successful" iterations, when an N-length auxiliary vector is updated, N being the problem size. The parallel design exploits the fact that element of the auxiliary vector call he updated simultaneously. As such an Update involves additions and bit-shifts only, the increase in complexity compared with the serial implementation is not significant, while the throughput call be enhanced. Two parallel designs are proposed; the first uses registers for the system matrix, while the second uses random access memory (RAM). The use of RAM significantly reduces the chip area (number of FPGA slices) without decreasing the throughput. The RAM design exploits the fact that, for the update of the auxiliary vector, only one row of the system matrix is used. The proposed parallel design is verified by applying to an MVDR antenna array beamformer. It is also compared with a QRD-based MVDR beamformer exploiting CORDIC processors. Antenna beampattern obtained from weights calculated in the fixed-point FPGA implementation is compared with a floating-point simulation. The comparison shows good match for a 9-element linear array. The proposed design call provide weight update rate as high as 27 kHz for a 9-element MVDR beamformer.

KW - FPGA

KW - DCD

KW - MVDR

KW - CORDIC

KW - parallel design

KW - normal equations

KW - multiplication-free

M3 - Conference contribution

SN - 978-1-4244-0881-8

SP - 331

EP - 334

BT - Proceedings of the 2007 15th International Conference on Digital Signal Processing

A2 - Sanei, S

A2 - Chambers, JA

A2 - McWhirter, J

A2 - Hicks, Y

A2 - Constantinides, AG

PB - IEEE

CY - NEW YORK

T2 - 15th International Conference on Digital Signal Processing

Y2 - 1 July 2007 through 4 July 2007

ER -