TY - GEN
T1 - Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching
AU - Qiu, Qinru
AU - Burns, Daniel
AU - Mukre, Prakash
AU - Wu, Qing
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - A large and reliable DNA codeword library is key to the success of DNA based computing. Searching for sets of reliable DNA codewords is an NP-hard problem, which can take days on state-of-art high performance cluster computers. This work presents a hybrid architecture that consists of a general purpose microprocessor and a hardware accelerator for accelerating the multi-deme genetic algorithm (GA) for the application of DNA codeword searching. The presented architecture provides more than 1000X speed-up compared to a software only implementation. A code extender that uses exhaustive search to produce locally optimum codes in about 1.5 hours for the case of length 16 codes is also described. The experimental results demonstrate that the GA can find ∼99% of the words in locally optimum libraries. Finally, we investigate the performance impact of migration, mating and mutation functions in the hardware accelerator. The analysis shows that a modified GA without mating is the most effective for DNA codeword searching.
AB - A large and reliable DNA codeword library is key to the success of DNA based computing. Searching for sets of reliable DNA codewords is an NP-hard problem, which can take days on state-of-art high performance cluster computers. This work presents a hybrid architecture that consists of a general purpose microprocessor and a hardware accelerator for accelerating the multi-deme genetic algorithm (GA) for the application of DNA codeword searching. The presented architecture provides more than 1000X speed-up compared to a software only implementation. A code extender that uses exhaustive search to produce locally optimum codes in about 1.5 hours for the case of length 16 codes is also described. The experimental results demonstrate that the GA can find ∼99% of the words in locally optimum libraries. Finally, we investigate the performance impact of migration, mating and mutation functions in the hardware accelerator. The analysis shows that a modified GA without mating is the most effective for DNA codeword searching.
KW - DNA
KW - Genetic algorithm
KW - Hardware acceleration
UR - http://www.scopus.com/inward/record.url?scp=34548098954&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548098954&partnerID=8YFLogxK
U2 - 10.1145/1276958.1277211
DO - 10.1145/1276958.1277211
M3 - Conference contribution
AN - SCOPUS:34548098954
SN - 1595936971
SN - 9781595936974
T3 - Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference
SP - 1349
EP - 1356
BT - Proceedings of GECCO 2007
T2 - 9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007
Y2 - 7 July 2007 through 11 July 2007
ER -