Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching

Qinru Qiu; Daniel Burns; Prakash Mukre; Qing Wu

doi:10.1145/1276958.1277211

Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching

Qinru Qiu, Daniel Burns, Prakash Mukre, Qing Wu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of GECCO 2007
Subtitle of host publication	Genetic and Evolutionary Computation Conference
Pages	1349-1356
Number of pages	8
DOIs	https://doi.org/10.1145/1276958.1277211
State	Published - 2007
Externally published	Yes
Event	9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007 - London, United Kingdom Duration: Jul 7 2007 → Jul 11 2007

Publication series

Name	Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference

Other

Other	9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007
Country	United Kingdom
City	London
Period	7/7/07 → 7/11/07

Keywords

DNA
Genetic algorithm
Hardware acceleration

ASJC Scopus subject areas

Artificial Intelligence
Software
Theoretical Computer Science

Access to Document

10.1145/1276958.1277211

Fingerprint Dive into the research topics of 'Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching'. Together they form a unique fingerprint.

Cite this

Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching. / Qiu, Qinru; Burns, Daniel; Mukre, Prakash; Wu, Qing.

Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference. 2007. p. 1349-1356 (Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Qiu, Q, Burns, D, Mukre, P & Wu, Q 2007, Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching. in Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference. Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference, pp. 1349-1356, 9th Annual Genetic and Evolutionary Computation Conference, GECCO 2007, London, United Kingdom, 7/7/07. https://doi.org/10.1145/1276958.1277211

@inproceedings{3afb49073e8b42f584068e6bc1b22c34,

title = "Hardware acceleration of multi-deme genetic algorithm for the application of DNA codeword searching",

abstract = "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.",

keywords = "DNA, Genetic algorithm, Hardware acceleration",

author = "Qinru Qiu and Daniel Burns and Prakash Mukre and Qing Wu",

year = "2007",

doi = "10.1145/1276958.1277211",

language = "English (US)",

isbn = "1595936971",

series = "Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference",

pages = "1349--1356",

booktitle = "Proceedings of GECCO 2007",

}

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

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 -