Abstract
Typical approaches to solve Dynamic Programming algorithms explore data level parallelism by relying on specialized vector instructions. However, the fully-parallelizable scheme is often not compliant with the memory organization of general purpose processors, leading to a less optimal parallelism exploitation, with worse performance. The proposed processor architecture overcomes this issue by relying on a data stream loader and a set of especially designed instructions. Furthermore, to make it compliant with the strict power and energy limitations of embedded systems, it maximizes resource utilization by exploiting both data and instruction level parallelism, by statically scheduling a bundle of instructions to several vector execution units. To evaluate the proposed architecture, we compare it with two embedded processors, an ARM Cortex-A9 and an application-specific processor with SIMD extensions, using two benchmarks from the sequence alignment domain, namely Smith-Waterman and Viterbi. The obtained results show that the proposed architecture achieves up to 5.16x and 2.19x better performance-energy efficiency and up to 5.44x and 1.25x better energy efficiency than the ARM Cortex-A9 and the dedicated processor, respectively.
This work was partially supported by national funds through Fundação para a Ciência e a Tecnologia (FCT), under projects: Threads (PTDC/EEAELC/117329/ 2010) and project UID/CEC/50021/2013.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Benson, D.A., Clark, K., Karsch-Mizrachi, I., Lipman, D.J., Ostell, J., Sayers, E.W.: Genbank. Nucleic Acids Research (2014)
Smith, T.F., Waterman, M.S.: Identification of Common Molecular Subsequences. Journal of Molecular Biology 147(1), 195–197 (1981)
Viterbi, A.: Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Transactions on Information Theory 13(2), 260–269 (1967)
Cardoso, F., Costa, T., Germano, J., Cardoso, S., Borme, J., Gaspar, J., Fernandes, J., Piedade, M., Freitas, P.: Integration of Magnetoresistive Biochips on a CMOS Circuit. IEEE Transactions on Magnetics 48(11), 3784–3787 (2012)
Farrar, M.: Striped Smith–Waterman Speeds Database Searches Six Times Over Other SIMD Implementations. Bioinformatics 23(2), 156–161 (2007)
Eddy, S.R.: Profile Hidden Markov Models. Bioinformatics 14(9), 755–763 (1998)
Neves, N., Sebastião, N., Matos, D., Tomás, P., Flores, P., Roma, N.: Multicore SIMD ASIP for Next-Generation Sequencing and Alignment Biochip Platforms. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems (in press) (2015)
Gotoh, O.: An improved Algorithm for Matching Biological Sequences. Journal of Molecular Biology 162(3), 705–708 (1982)
Xilinx.: Xilinx DS190 Zynq-7000 All Programmable SoC Overview (2013), http://www.xilinx.com/support/documentation/data_sheets/ds190-Zynq-7000-Overview.pdf (last accessed on December 10, 2014)
Finn, R.D., Bateman, A., Clements, J., Coggill, P., Eberhardt, R.Y., Eddy, S.R., Heger, A., Hetherington, K., Holm, L., Mistry, J., et al.: Pfam: The Protein Families Database. Nucleic Acids Research, gkt1223 (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Cruz, M.T., Tomás, P., Roma, N. (2015). Energy-Efficient Architecture for DP Local Sequence Alignment: Exploiting ILP and DLP. In: Ortuño, F., Rojas, I. (eds) Bioinformatics and Biomedical Engineering. IWBBIO 2015. Lecture Notes in Computer Science(), vol 9044. Springer, Cham. https://doi.org/10.1007/978-3-319-16480-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-16480-9_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16479-3
Online ISBN: 978-3-319-16480-9
eBook Packages: Computer ScienceComputer Science (R0)