Yuanwu Lei

As one of the most important and computationally-intensive parts in bioinformatics analysis, the Pair Hidden Markov Model (Pair-HMM) forward algorithm is widely recognized and has great potential. Therefore, it is important to accelerate the process of this algorithm. There are various approaches to accelerate Pair-HMM, especially the accelerators stemmed from the Field Programmable Gate Array (FPGA) due to the highly-customizable on-chip resources and deep pipeline potential available to the designer. In this paper, we focus on the FPGA-based accelerators for the Pair-HMM forward algorithm proposed in recent years. The non-cooperation structure, which was proposed in our previous work, is compared with the Systolic Array (SA) structure and PE ring structure in the structure characteristics, calculation mode, computational efficiency, and storage requirement. We build an analysis model to evaluate the performance of the ring structure and our non-cooperative structure. Furthermore, based on this, we provide a detailed analysis of the characteristics of structures of different accelerators and of the selection of a suitable structure for different scenarios. Based on the non-cooperative PE structure, we design a new chain topology for the accelerator. Experimental results show that our non-cooperation structure is superior to the other structures in performance and execution efficiency, and our new topology improves the performance of the accelerator. Finally, we propose some ideas about the improvement of the non-cooperative structure accelerator for future work.

Matrix transposition plays a critical role in digital signal processing. However, existing matrix transposition implementations have significant limitations. A traditional design uses load and store instructions to accomplish matrix transposition. Depending on the amount of load/store units, this design typically transposes up to one matrix element per clock cycle. More seriously, this design cannot perform matrix transposition and data calculations in parallel. Modern digital signal processors (DSPs) integrate the support for matrix transposition into the direct memory access (DMA) controller; the matrix can be transposed during data movements. It allows the parallel execution of matrix transposition and data calculations. Yet, its bandwidth utilization is limited; it can only transfer one matrix element per clock cycle. To address the limitations of existing designs, we propose MT-DMA, to support efficient matrix transposition in DMA controllers. It can transpose multiple matrix elements per clock cycle to improve the bandwidth utilization. Compared with existing designs, MT-DMA achieves a maximum 23.9 times performance improvement for micro-benchmarks. It is also more energy efficient. Since MT-DMA effectively hides the latency of matrix transposition behind data calculations, it performs very closely to an ideal design for real applications.

Focused on the issue that division is complex and needs a long latency to compute, a method to design the unit of high-performance Floating-point (FP) divider based on Goldschmidt algorithm was proposed. Bipartite reciprocal tables were adopted to obtain initial value of iteration with area-saving, and parallel multipliers were employed in the iteration unit to reduce latency. FP divider to support pipeline execution with the control of state machine is presented to increase the throughput. The design was implemented in Digital signal process (DSP) chip by sharing the existed multipliers.

CORDIC algorithm is suitable to implement sine/cosine function, but the large number of iterations lead to great delay and overhead. Moreover, due to finite bit-width of operands and number of iterations, the relative error of floating-point sine or cosine is terrible when the input angle is close to 0 or π/2, respectively. To overcome these shortcomings, TCORDIC algorithm, which combines low latency CORDIC and Taylor algorithm, is presented. After analyzing the latency of traditional CORDIC, low latency CORDIC is proposed, which adopts the technique of sign prediction, compressive iterations, and parallel iterations. Besides, the calculating boundary (N), which is used for determining whether Taylor algorithm is selected or not in TCORDIC algorithm, is evaluated to achieve a trade-off between area and delay. Truncated multipliers are used to reduce the area further. Finally, Using TCORDIC algorithm, pipelined and iterative structures are implemented for IEEE-754 double precision floating-point sine/cosine with the input Zϵ[0, π/2]. Under typical condition (1V, 25 °C), our designs are synthesized with 40 nm standard cell library. For a pipelined structure, the frequency is up to 1.70 GHz and area 194049.64 μm ² . Frequency decreases to 1.45 GHz for iterative structure, but the area requires only 110590.81 μm ² . TCORDIC is efficient in controlling relative error, and achieves the accuracy within one ulp (unit in the last place) for floating-point sine/cosine function.