Disease Diagnosis-on-a-Chip: Large Scale Networks-on-Chip based Multicore Platform for Protein Folding Analysis

ABSTRACT

Protein folding is critical for many biological processes. In this work, we propose an NoC-based multi-core platform for protein folding computation. We first identify the speedup bottleneck for applying conventional genetic algorithm on a mesh-based multi-core platform. Then, we address this computation- and communication- intensive problem while taking into account both hardware and software aspects. Specifically, we group the processing cores into islands and propose an NoC-based multicore architecture for intra- and inter-island communication. The high scalability of the proposed platform allows us to integrate from 100 to 1200 cores for the folding computation. We then propose a genetic migration algorithm to take advantage of the massive parallel platform. Our simulation results show that the proposed platform offers near-linear speedup as the number of cores increases. We also report the hardware cost in area and power based on a 100-core FPGA prototype.

References

1. J. Atkins and W. E. Hart. On the intractability of protein folding with a finite alphabet of amino acids. Algorithmica, 25(2-3):279--294, 1999.
2. A. Beberg et.al. Folding@home: Lessons from eight years of volunteer distributed computing. In Proc. IPDPS 2009., pages 1--8, 2009.
3. C. Benitez and H. Lopes. A parallel genetic algorithm for protein folding prediction using the 3d-hp side chain model. In Evolutionary Computation, 2009. IEEE Congress on, pages 1297--1304, 2009.
4. C. Benitez and H. Lopes. Hierarchical parallel genetic algorithm applied to the three-dimensional hp side-chain protein folding problem. In Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, pages 2669--2676, 2010.
5. K. A. Dill and J. L. MacCallum. The protein-folding problem, 50 years on. Science, 338(6110):1042--1046.
6. S. C. Flores et.al. Multiscale modeling of macromolecular biosystems. Brief Bioinform, 13(4):395--405, 2012.
7. A. Jain et.al. Fpga accelerator for protein structure prediction algorithm. In Programmable Logic, 5th Southern Conference on, pages 123--128, 2009.
8. Z. Li and H. A. Scheraga. Monte carlo-minimization approach to the multiple-minima problem in protein folding. PNAS, 84(19): 6611--6615, 1987.
9. R. Marculescu and P. Bogdan. The chip is the network: Toward a science of network-on-chip design. Foundations and Trends in Electronic Design Automation, 2(4):371--461, 2009.
10. D. E. Shaw et.al. Anton, a special-purpose machine for molecular dynamics simulation. In Proc, ISCA '07, pages 1--12, 2007.
11. W.-T. Sung. Efficiency enhancement of protein folding for complete molecular simulation via hardware computing. In Bioinformatics and BioEngineering, 2009., pages 307--312.
12. R. Unger and J. Moult. Genetic algorithm for 3d protein folding simulations. In Proceedings of the 5th International Conference on Genetic Algorithms, pages 581--588, 1993.
13. K. D. Wilkinson. The discovery of ubiquitin-dependent proteolysis. Proceedings of the National Academy of Sciences of the United States of America, 102(43): 15280--15282, 2005.
14. K. Yue et.al. A test of lattice protein folding algorithms. PNAS, 92(1):325--329, 1995.