24_10.dvi

Size: px

Start display at page:

Download "24_10.dvi"

あおいさだい
7 years ago
Views:

1 Vol. 1 No (Dec. 2008) FPGA SSA SSA FPGA SSA Next Reaction Method NRM FPGA FPGA 16 HSR RTL Core 2 Quad Q GHz 4.2 HSR 5.4 Design and Evaluation of an FPGA-based Stochastic Biochemical Simulator for High-throughput Execution Masato Yoshimi, 1 Yuri Nishikawa, 1 Yasunori Osana, 2 Akira Funahashi, 1 Noriko Hiroi, 3 Yuichiro Shibata, 4 Hideki Yamada, 4 Hiroaki Kitano 5 and Hideharu Amano 1 Stochastic biochemical simulation algorithms (SSAs) are generally known as exact methods to trace stochastic behaviors of target biochemical models. Due to vast amount of computation attributed to the nature of Monte Carlo Method, which SSAs are originated from, there is a strong urge for high-throughput execution environment. This paper proposes an FPGA implementation of a stochastic simulation system based on a computationally-efficient SSA called the Next Reaction Method, and studies the evaluation results of area and throughput in detail. The system conducts high-throughput multi-thread execution, using multiple thread modules accessing shared arithmetic and data modules. The network between modules are configurable, and supports flexible network structure according to target FPGAs. In order to evaluate the proposed design, the stochastic simulation system, which is capable of running 16 threads in parallel, was implemented on a middle-range FPGA. As the result of comparing the throughput in RTL simulation with software simulation run on Core 2 Quad Q6600, the system marked 4.2 times higher throughput using a real biochemical model called HSR. When several versions of virtually largescale models were tested on the same simulation environment, maximum of 5.4 times higher throughput was confirmed. 1. Stochastic Biochemical Simulation Algorithm SSA SSA FPGA Field Programmable Gate Array FPGA 1 Graduate School of Science and Technology, Keio University 2 Faculty of Science and Technology, Seikei University 3 European Molecular Biology Laboratory, European Bioinformatics Institute, Wellcome Trust Genome Campus 4 Department of Computer and Information Sciences, Nagasaki University 5 Kitano Symbiotic Systems Project, ERATO-SORST, Japan Science and Technology Agency 120 c 2008 Information Processing Society of Japan

2 121 FPGA 1) 4) Next Reaction Method NRM FPGA 5) 7) NRM FPGA 2. SSA: Stochastic Biochemical Simulation Algorithm 2.1 M N M R j j 1, 2,,M (1) R j : S a + S b c j S c + S d (1) S i i =0,,N c j (1) (1) t S i X i SSA 1 2 (1) (2) 1 M 2.2 NRM: Next Reaction Method Gillespie 8) SSA Gibson Next Reaction Method NRM 9) NRM First Reaction Method SSA FRM (2) τ j τ j =ln(1/r) /a j + t (2) r (0, 1) t a j R j 2 propensity NRM 2 SSA O(M) O(log(M)) Indexed Priority Queue IPQ 2 Dependency Graph DG DG NRM 1 τ j IPQ IPQ DG 1 NRM 2 Fig. 1 An operation procedure of one reaction cycle in NRM after the second reaction cycle.

3 122 FPGA (2) 1 U4 DG τ j,new propensity a j,old a j,new IPQ τ j,old 3 a j,new =0 R j τ j,new = a j,old =0 a j,new 0 (2) U4 τ j,new (3) U5 τ j,old τ j,new = a j,old (τ j,old t)/a j,new + t (3) DG IPQ IPQ NRM 1 DG SSA 2 O(log(M)) E-Cell3 10) COPASI 11) NRM SSA NRM 9) Cao Optimized Direct Method 12) explicit/implicit τ-leaping 13) SBML MATLAB StochKit 14) FPGA Gillespie 1) 3) FPGA 4) PC 15) GPU 14) 2004 FPGA SSA 16) 2006 NRM 5) 3.2 FPGA SSA FPGA SSA Keane 3) SSA 1 3 M =32 Pentium4 2.0 GHz NRM 20 1 Keane FPGA Thurmon DIMM FPGA Direct Method SSA DM propensity FPGA PC FPGA 4) M =14 Pentium III 1 GHz C++ FRM 10 NRM 2.24 PC FPGA 3.3 FPGA First Reaction Method FPGA FRM FRM-FPGA 17) FRM-FPGA 1 FRM 1 2 FRM FPGA 3

4 123 FPGA Table 1 1 FRM-FPGA Evaluation environment of FRM-FPGA. FRM-UNIT 3 FRM-UNIT 2 6 FPGA Virtex-II Pro XC2VP MHz 33,088 Slices 24, % BlockRAM Table 2 2 C++ Execution environment of C++ program code. CPU Memory OS Compiler Intel Core 2 Quad Q GHz 3.5 GB 4.0 GB Linux x86-32bit gcc O3 1 2 Mcycles/sec Fig. 2 Throughput comparison (unit: Mcycles/sec). DG (2) 6 FPGA Virtex-II Pro BlockRAM BlockRAM M = 1024 FRM NRM C++ FRM-SW NRM-SW CPU FRM-FPGA 2 2 FRM-FPGA RTL Lotka 18) M =4 N =4 M 2 n Lotka nlotka 2 FRM-FPGA 1Lotka M =4 FRM-SW Lotka M =64 40 FRM M 32 Lotka M = 128 NRM FRM 9) FRM-FPGA NRM NRM SSA 12) NRM NRM FPGA NRM-FPGA 4. FPGA NRM FPGA NRM NRM 4.1 NRM NRM 2 NRM-SW 3 1 4

5 124 FPGA Fig. 4 4 NRM Number of function calls in NRM. 3 NRM HSR Fig. 3 Calculation time and its breakout for HSR model in NRM. 2 Lotka E.coli Heat-Shock Response HSR M =61 N =28 nhsr n HSR M 1000 HSR Cao SSA StochKit 14) M IPQ 2 NRM DG DG 4 HSR propensity IPQ U3 HSR DG 4.2 FPGA NRM 3 NRM NRM 24 M KB 20 M KB 4 M KB NRM FPGA FPGA PC PC FPGA NRM

6 125 FPGA NRM 1 1 FPGA BlockRAM I/O NRM NRM FPGA 5 NRM NRM U1 U2 U3 U4 U5 1 MUX 6) MUX 1 Network-on-Chip NoC 7) NoC BlockRAM 5 NRM Fig. 5 Module connection diagram of NRM execution system. 5.5 Distributor Concentrator 5. NRM NRM Verilog-HDL Xilinx CORE Generator BlockRAM FIFO

7 126 FPGA NRM 6 IPQ Propensity 3 1,024 Dual-port BlockRAM M = 1023 N = 1024 M = 1024 IPQ 2 0 IPQ 2 10-bits bits IPQ 2 IPQ 5 FIFO BlockRAM 5.3 NRM FIFO 8 FIFO START 1 U1 U2 IPQ 2 U1 U2 5 IDLE FIFO FIFO FETCH FIFO U1 6 Fig. 6 Structure of the threaded module. Fig State transition of the packet controller and send/receive packet in a reaction cycle.

8 127 FPGA U2 U1 U3 U3 L U1 U2 U3 Propensity propensity a j,old a j,new τ j,old U4 U5 IPQ 2 U1 IPQ IPQ U1 U2 U3 U4 U U2 2 U FIFO U1 U U2 Dependency Graph 1 Fig. 8 Structure of shared module U2 (Dependency Graph) with a set of I/O port U4 9 (2) (0, 1) Linear Feedback Shift Register LFSR M (1, 2) 1.0 e 2 FIFO U3 U5 U % U1 U2 1 U1 U2 1

9 128 FPGA Fig. 9 9 U4 τ 2 Structure of shared module U4 (calculates τ) with two sets of I/O port. U1 U Concentrator Distributor Concentrator Distributor 10 4 Fig. 10 Examples of 4-port interconnection modules.

10 129 FPGA 34-bit 2 FIFO Concentrator 1 Distributor 5.6 NRM NRM 11 4 NRM p 1 1 Concentrator Distributor Tp NRM Tp p Tp 4 U3 U3 T16 T16C T16C U3 4 U3C 4 4 Concentrator Distributor U3 6. FPGA TB-5V-LX110T- PCIEXP 19) FPGA XC5VLX110T-FF1136 NRM Xilinx ISE8.2i RTL FPGA FPGA LUT 2.1% = 1283/ BlockRAM 4.1% FPGA Table 3 3 Area and operating frequency of each module NRM Fig. 11 Structure of NRM execution system with 4 threaded modules. Thread U1 U2 U3 U4 U5 U3C Registers ,028 7,231 2,857 1,620 LUTs 1, ,154 2,111 1,774 BlockRAM/FIFO DSP48Es Max. Delay [ns] Op. Freq. [MHz] XC5VLX110T-FF1136: Slice 69,120: LUTs 69,120: BlockRAM/FIFO 148: DSP48E 64

11 130 FPGA Table 4 4 NRM Operation frequency of NRM execution system. [MHz] T T T T T T T16C Fig NRM Resource utilization of NRM execution system. FPGA BlockRAM U1 U2 BlockRAM U3 U4 U5 6.2 NRM NRM T20 FPGA 4 FPGA T8 3 T16 T20 T16C NRM Concentrator Distributor LUT T16 T16C Slice Register 1, % LUT Fig Average number of clock cycles to calculate one reaction cycle.

12 131 FPGA 15 % Fig. 15 Operation rate of each functional core (unit: %). U3C 6.3 NRM NRM 4.1 HSR n nhsr 50,000 RTL T16 T20 14 U3 15 T16 T20 U3 33.3% Fig Average waiting time to transfer each packet.

13 132 FPGA 4 U3C 100% T16C U3 4 HSR IPQ U3 U NRM StochKit DM FPGA 1 13 T1 T8 150 MHz T16 T16C 135 MHz T MHz T1 T8 16 T20 T16 T16C U3 3 IPQ NRM HSR FPGA T8 2 2 T8 2 T16C FPGA T16C NRM-SW StochKit HSR DM NRM-SW M Next Reaction Method FPGA NRM NRM 16 Mcycles/sec Fig. 16 Comparison of throughput (unit: Mcycles/sec). HSR Core 2 Quad Q GHz

14 133 FPGA NRM 4.2 HSR 5.4 NRM SSA 12) PC 1) Lok, L.: The need for speed in stochastic simulation, Nature Biotechnology, Vol.22, No.8, pp (2004). 2) Salwinski, L. and Eisenberg, D.: In silico simulation of biological network dynamics, Nature Biotechnology, Vol.22, No.8, pp (2004). 3) Keane, J.F., Bradley, C. and Ebeling, C.: A Compiled Accelerator for Biological Cell Signaling Simulations, The 12th Int. Symp. on Field-Programmable Gate Arrays (FPGA), pp (2004). 4) Thurmon, B.P., McCollum, J.M., Peterson, G.D., Cox, C.D., Samatova, N.F., Sayler, G.S. and Simpson, M.L.: Accelerating Exact Stochastic Simulation using Reconfigurable Computing, International Conference on Engineering of Reconfigurable Systems and Algorithms (2005). 5) Yoshimi, M., Osana, Y., Iwaoka, Y., Nishikawa, Y., Kojima, T., Funahashi, A., Hiroi, N., Shibata, Y., Iwanaga, N., Kitano, H. and Amano, H.: An FPGA Implementation of High Throughput Stochastic Simulator for Large-Scale Biochemical Systems, The 16th International Conference on Field Programmable Logic and Applications (FPL 06 ), pp (2006). 6) Yoshimi, M., Iwaoka, Y., Nishikawa, Y., Kojima, T., Osana, Y., Funahashi, A., Hiroi, N., Shibata, Y., Iwanaga, N., Yamada, H., Kitano, H. and Amano, H.: FPGA Implementation of a data-driven Stochastic Biochemical Simulator with the Next Reaction Method, The 17th International Conference on Field Programmable Logic and Applications (FPL 07 ), IEEE, pp (2007). 7) Yoshimi, M., Nishikawa, Y., Kojima, T., Osana, Y., Funahashi, A., Hiroi, N., Shibata, Y., Yamada, H., Kitano, H. and Amano, H.: A Framework for Implementing a Network-Based Stochastic Biochemical Simulator on an FPGA, International Conference on Field-Programmable Technology (ICFPT 07 ), pp (2007). 8) Gillespie, D.T.: A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Reactions, Journal of Computational Physics, Vol.22, pp (1976). 9) Gibson, M.A. and Bruck, J.: Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channels, JournalofPhysicalChemistryA, Vol.104, No.9, pp (2000). 10) Takahashi, K., Yugi, K., Hashimoto, K., Yamada, Y., Pickett, C.J.F. and Tomita, M.: A multi-algorithm, multi-timescale method for cell simulation, Bioinformatics, Vol.20, No.4, pp (2004). 11) Hoops, S., Sahle, S., Gauges, R., Lee, C., Pahle, J., Simus, N., Singhal, M., Xu, L., Mendes, P. and Kummer, U.: COPASI a COmplex PAthway SImulator, Bioinformatics, Vol.22, No.24, pp (2006). 12) Cao, Y., Li, H. and Petzold, L.: Efficient formulation of the stochastic simulation algorithm for chemically recting systems, JournalofChemicalPhysics, Vol.121, No.9, pp (2004). 13) Gillespie, D.T.: Stochastic Simulation of Chemical Kinetics, Annual Review of Physical Chemistry, Vol.58, pp (2007). 14) Li, H., Cao, Y., Petzold, L.R. and Gillespie, D.T.: Algorithms and Software for Stochastic Simulation of Biochemical Reacting Systems, Biotechnology Progress, Vol.24, No.1, pp (2007). 15) Schwehm, M.: Parallel Stochastic Simulation of Whole-Cell Models, Proc. 2nd International Conference on Systems Biology, pp (2001). 16) Yoshimi, M., Osana, Y., Fukushima, T. and Amano, H.: Stochastic Simulation for Biochemical Reactions on FPGA, The 14th International Conference on Field Programmable Logic and Applications, Lecture Notes in Computer Science, Vol.3203, pp , Springer (2004). 17) FPGA Vol.48, No.SIG 3 (ACS 17), pp (2007). 18) Gillespie, D.T.: Exact Stochastic Simulation of Coupled Chemical Reactions, The JournalofPhysicalChemistry, Vol.81, No.25, pp (1977). 19) Tokyo Electron Device: Virtex-5 LXT/SXT PCI Express Evaluation Platform Board. ( ) ( )

15 134 FPGA European Bioinformatics Institute EMBL-EBI IEEE-CS 2006 IEEE-CS IEEE IEEE-CS 1991

16 135 FPGA 1986 IEEE

,4) 1 P% P%P=2.5 5%!%! (1) = (2) l l Figure 1 A compilation flow of the proposing sampling based architecture simulation

,4) 1 P% P%P=2.5 5%!%! (1) = (2) l l Figure 1 A compilation flow of the proposing sampling based architecture simulation 1 1 1 1 SPEC CPU 2000 EQUAKE 1.6 50 500 A Parallelizing Compiler Cooperative Multicore Architecture Simulator with Changeover Mechanism of Simulation Modes GAKUHO TAGUCHI 1 YOUICHI ABE 1 KEIJI KIMURA 1