a new drug to market usually costs a lot of time for the research and the development and invests a huge amount of money . after decoding the human genome , the molecular biology and
the proteomic fields make a remarkable advance ; people understand more clearly the disease generation and the disease mechanism
. computer - aided drug design ( abbreviated to cadd )   becomes an emerging research field , and it is helpful to improve the efficiencies of drug design and development .
rational drug design is based on the structure , the property , and the mechanism .
there are two major approaches : structure - based approach and ligand - based approach .
structure - based approach mainly uses the techniques of docking [ 2 , 3 ] and de novo ligand design , and the ligand - based approach uses the techniques of qsar   and pharmacophore [ 3 , 6 ] mostly . based on these two approaches ,
after that , in general , these potential inhibitors will be used to compare with the compound databases , such as zinc , pubchem , and gdb-13 , in order to find other compounds with similar structure .
these similar compounds may be helpful for shortening the subsequent synthesis procedures of potential inhibitors .
the potential inhibitors and similar compounds are then used for the pharmacy experiments to test the biological activity , toxicity , and so forth . for well - known drugs ,
therefore , compound comparison has been an important and commonly used task for the computational chemistry .
the tanimoto coefficient is one of the most popular measurements between two molecules ( compounds ) due to its computational efficiency and its relevance to biological profile [ 11 , 12 ] . in most of the works
, molecules can be represented as fingerprints and smiles , and then the work of compound comparison can be seen as the string comparison problem .
for example , the lingo method   proposed by vidal et al . is a simple algorithm to compute the chemical similarity between two smiles - based molecules , and it has demonstrated the accuracy comparable to fingerprint methods . for a pairwise compound comparison ,
the time complexity is o(n ) , where n is the maximal length of compounds . in general , the length of compound is short ( e.g. , tens to hundreds ) and the computation time is small .
however , it will be time - consuming when compared with a large amount of compounds ( denoted by a multiple compound comparison problem , abbreviated to mcc ) , such as zinc database with more than 60 million compounds and gdb-13 database with more than 970 million small molecules .
the intrinsic time complexity of mcc problem is o(kn ) with k compounds of maximal length n. hence , how to accelerate the mcc problem is an important issue .
it is a feasible direction to apply parallel technologies and multicore devices into the above issue .
the feasibility of using massive computational devices to enhance the performance of many programs has received considerable attention in recent years , especially for many - core devices , such as fpgas [ 1517 ] and cell / bes [ 1820 ] . current high - end graphics processing units ( abbreviated to gpus ) [ 21 , 22 ] , which contain up to thousands of cores per chip , are widely used in the high performance computing community . as a massively multithreaded processor , gpu expects the thousands of concurrent threads to fully utilize its computing power .
the ease of accessing gpus by using general - purpose computing on graphics processing units ( abbreviated to gpgpu ) such as open computing language ( abbreviated to opencl , https://www.khronos.org/opencl/ ) and compute unified device architecture ( abbreviated to cuda ) , as opposed to graphic apis ( as opengl ) , has made the supercomputing available widely .
cuda uses a new computing architecture referred to as single instruction multiple threads ( simt ) , which differs from flynn 's classification .
importantly , the computing power and the memory bandwidth for modern gpus have made porting applications more possible . for the mcc problem
, it can be done to compare a compound with a set of compounds ( denoted by one to all , abbreviated to o2a ) or to compare two sets of compounds ( denoted by all to all , abbreviated to a2a ) .
proposed a gpu - based parallel algorithm , called siml ( full name is single - instruction multiple - lingo ) , to calculate the tanimoto coefficients between smiles - based molecules .
the siml algorithm is designed based on the lingo method , and its gpu implementation is over 30 times faster than its cpu version .
ma et al . presented a parallel algorithm   to calculate the tanimoto coefficients for mcc problem between molecular fingerprints on gpus .
the experimental results showed that the implemented program achieved 39 times faster than sybyl database comparison program that runs on cpus and 10 times faster than other gpu - based programs [ 25 , 27 ] .
however , it is unfair to compare their algorithm based on the fingerprints representation with other algorithms based on the smiles representation .
the reason is that the computation is different for these two representations . among these works , it is still insufficient for designing a gpu - based algorithm for mcc problem . at first ,
third , they did not apply various load - balancing strategies into their works and then discuss their effects . a suitable load - balancing strategy
hence , in this paper , we propose a gpu - based algorithm for mcc problem ( o2a and a2a ) on single- and multi - gpus , called cuda - mcc . as the work , cuda - mcc
is also based on the lingo method to calculate the tanimoto coefficients between smiles - based molecules .
four lingo - based load - balancing strategies were also applied into cuda - mcc by considering the lingo score , lingo number , lingo length , and lingo magnitude , respectively .
the experimental tests were done on single nvidia tesla k20 m gpu card and dual - nvidia tesla k20 m gpu cards , and the experimental results showed that cuda - mcc can achieve 45 times and 391 times faster than its cpu version on the above experimental environments , respectively .
the lingo method is to model a molecule as a collection of substrings of smiles representation ( seen as a string ) .
thus , a smiles string is fragmented into all substrings with length of q by using the sliding window scheme .
in addition , the information of each q - lingo is also stored in order to do the following comparison .
for example , as shown in the literature , the score , length , number , and magnitude of each q - lingo are stored . when doing the pairwise compound comparison , two sets of q - lingos from two molecules
are used to find the same lingos . the number of the same lingos is then used to calculate the tanimoto coefficients .
the details of lingo method can be found in the literature . therefore , there are four lingo - based load - balancing strategies by considering the score , length , number , and magnitude of each molecule represented by q - lingos .
cuda is an extension of commonly used programming languages , such as c / c++ , in which users can write scalable multithreading programs for various applications . in general , the cuda program is implemented in two parts : host and device .
the host part is executed on cpu , and the device part is executed on gpu . the function executed on the device part is called a kernel .
these threads are grouped into a hierarchical organization which can be combined into thread blocks and grids .
a grid is a set of independent thread blocks , and a thread block contains many threads .
the size of grid is the number of thread blocks per grid , and the size of thread block is the number of threads per thread block .
threads within a thread block can communicate through a per thread block shared memory , whereas threads in the different thread blocks fail to communicate or synchronize directly . besides shared memory ,
five memory types are per grid private local memory , global memory for data shared by all thread blocks , texture memory , constant memory , and registers . of these memory types
, constant memory and texture memory can be regarded as fast read only caches ; the fastest memories are the registers and shared memory .
the global memory , local memory , texture memory , and constant memory are located on the gpu 's memory . besides shared memory accessed by a single thread block and
register only accessed by a single thread , the other memory types can be used by all of the threads .
the caches of texture memory and constant memory are limited to 8  kb per streaming multiprocessor .
the optimum access strategy for constant memory is all threads reading the same memory address .
the cache of texture memory is designed for threads to read through the proximity of the address in order to achieve an improved reading efficiency .
fermi and kepler architectures have real configurable l1 per streaming multiprocessor and unified l2 caches among streaming multiprocessors .
hence , l2 caches can be accessed by global memory and each streaming multiprocessor can use the l1 caches and shared memory . the basic processing unit in nvidia 's gpu architecture
several streaming processors can be integrated into a streaming multiprocessor according to various architectures , such as 32 and 192 streaming processors per streaming multiprocessor for fermi and kepler architectures , respectively . while the program runs the kernel , the device schedules thread blocks for the execution on the streaming multiprocessor .
the simt scheme refers to threads running on the streaming multiprocessor in a small group of 32 , called a warp .
in cuda - mcc , the goal is to compare two sets of compounds ( a2a ) listed as query and database at first and then find the compounds in database with more than 0.85 tanimoto coefficients for each compound in query .
cuda - mcc also can be used to do the o2a comparison when the query is with only one compound . for each compound in query and database
, it should be fragmented into a set of q - lingos mentioned in section 2 , respectively .
have demonstrated that setting q = 4 can have the best performance in various cheminformatics applications .
hence , in cuda - mcc , the q is set to 4 . since this procedure
is only done once , a preprocessing phase is designed in cuda - mcc to do this procedure on cpu .
after this phase , the information of query and database is transferred from cpu to gpu , and then a gpu implementation of comparison phase is designed in cuda - mcc in order to accelerate the computation speed .
finally , the tanimoto coefficient of each pair of compounds is stored in a result array on gpu , and then this result array will be transferred from gpu to cpu .
all the compounds in database with more than 0.85 tanimoto coefficients for each compound in query are reported in the output phase on cpu .
the flowchart of three phases in cuda - mcc is shown in figure 1 . in figure 1 , the first three processes for query and database are the preprocessing phase , followed by the comparison phase , and output phase which is the last phase .
this phase can be divided into three parts : reading files , lingo construction , and lingo sorting . in the reading files part
, there are two databases query and database , as input files should be read from the disk to memory space on cpu .
for these two databases , the compounds are stored in two - dimensional string arrays , q and db , respectively . in q and db ,
after that , in the lingo construction part , each smiles code ( as a string ) is fragmented into a set of 4-lingos ( as substrings ) by using the sliding window scheme with an offset 1 on cpu . for a 4-lingo , it will be transformed into a 32-bit integer ( called lingo score ) according to the ascii code table in order to accelerate the comparison in the comparison phase . for a smiles code with length l
, it can be fragmented into l-3 4-lingos and this value l is called lingo length .
hence , for a smiles code , a temporary one - dimensional integer array and an integer variable are used to store the lingo score of each 4-lingo and lingo length , respectively .
since there are possible repeats ( for each 4-lingo ) in this array , the number of repeats for each 4-lingo is calculated .
an integer variable , lingo number , for each lingo score , is used to record the times of a 4-lingo appearing in this compound ; for example , for a 4-lingo , 1 represents only once and two or more represents the repeats .
the number of 4-lingos without repeats is also calculated and then recorded in an integer variable , lingo magnitude . for a compound
, there are four lingo types : lingo scores , lingo length , lingo numbers , and lingo magnitude .
an example of a smiles code in the preprocessing phase is shown in figure 2 . in order to simplify the figure ,
the remaining lingo scores of nine 4-lingos are omitted in figure 2 . in this case , the lingo number is 1 for each 4-lingo .
the lingo length is 13 and the lingo magnitude is 10 which is equal to the number of 4-lingos . for a pair of compounds , the tanimoto coefficient is calculated according to the number of similar 4-lingos .
therefore , in order to accelerate the computation and reduce the unnecessary comparisons in the comparison phase , for each compound , its lingo scores are sorted by using the quick sort algorithm on cpu in the lingo sorting part .
therefore , for query and database , a two - dimensional integer array is used to store the sorted lingo scores of each compound ( 4-lingos ) ; a two - dimensional integer array is used to store the lingo numbers of each 4-lingo ; a one - dimensional integer array is used to store the lingo lengths of each compound ; a one - dimensional integer array is used to store the lingo magnitudes of each compound .
these arrays mentioned above can be packaged in a complex structure array ( lingo constructor ) .
the information was stored in a complex structure array for query and database , respectively , as shown in figure 1 .
the pseudocodes of lingo constructor , lingo number , lingo score , lingo magnitude , and lingo length are listed  in pseudocode 1 . in this paper
therefore , the above three parts are all done on cpu in order to simplify the problem in cuda - mcc . in practice
when the second part is implemented on gpu , the memory usage should be considered . since
the number of lingo magnitudes is unknown after the reading files part , the fixed ( large ) memory space of structure array in each compound should be allocated on gpu at first . by this way
four lingo types of each compound can be calculated by a thread ; hence , thousands of concurrent threads can be used to process these compounds quickly .
after that , the wasted memory space could be removed by the memory reallocated procedure and the prefix sum algorithm .
it is easy to reallocate the previous structure array into a new one on gpu by all threads according to the indices , which is computed by gpu - based prefix sum algorithm published in the past .
for the implementation of the third part on gpu , many gpu - based sorting algorithms have been proposed in the past .
these gpu - based sorting algorithms can be modified to sort these lingo scores quickly on gpu . in the following experimental tests , the computation time of preprocessing phase
is not included in the time analysis ; it only includes the time of comparison phase and output phase . before designing the comparison phase in cuda - mcc , how to assign the comparison tasks on gpus should be discussed . to compare two sets of compounds (
a2a ) can be seen as to compare a compound with a set of compounds repeatedly ( o2a ) .
therefore , in cuda - mcc , a compound in query will be used to compare with all compounds in database by all threads on gpus when executing the kernel function once . in a thread block , each thread is used to compare a compound in query with one of the compounds in database . hence , the computing workload of each thread in a thread block should be equal in order to achieve the high performance . for multi - gpus , the computing workload of each gpu card should also be the same .
a load - balancing strategy can be used to accelerate the computation speed for single- and multi - gpu cards . however ,
how to estimate the computing workload of a comparison is a problem , since only a compound in query is used when executing the kernel function once .
the lingo length and lingo magnitude can be used directly as the measurements of computing workloads .
the sums of lingo scores and lingo numbers can be calculated as shown in the pseudocodes of preprocessing phase , respectively , and then they are used as other measurements of computing workloads .
four lingo - based load - balancing strategies are applied into cuda - mcc by considering these four lingo types .
as mentioned in the preprocessing phase , the list of compounds in database ( structure array of database ) is sorted on cpu . in the comparison phase , on single - gpu ,
the structure arrays of query ( q ) and database ( db ) are transferred from cpu to gpu by using the following two libraries :  cudamemcpy(db_d , db , sizeof(struct lingo)db_type , cudamemcpyhosttodevice ) ;  cudamemcpy(q_d , q , sizeof(struct lingo)q_type , cudamemcpyhosttodevice ) .
cudamemcpy(db_d , db , sizeof(struct lingo)db_type , cudamemcpyhosttodevice ) ; cudamemcpy(q_d , q , sizeof(struct lingo)q_type , cudamemcpyhosttodevice ) .
the time of transferring structure arrays from cpu to gpu is included in the time of comparison phase . a two - dimensional floating point array ( result array ) with a size of k  r , where k and r are the number of compounds in query and database , respectively , is created in the global memory .
this array is used to store the computed tanimoto coefficient for each comparison . for each comparison ,
the sorted lingo scores of a compound in query are used to compare with other sorted lingo scores of a compound in database .
it is a simple job to find the same lingo scores among these two compounds . by accumulating the lingo numbers corresponding to the same lingo scores
on multi - gpus , the structure array of query will be divided into several parts according to the computing capabilities of gpu cards .
then , these structure subarrays of query are transferred from cpu to the global memory of the corresponding gpu , respectively .
the complete structure array of database also is transferred from cpu to the global memory of each gpu , respectively . for each gpu , a two - dimensional floating point array ( partial result array ) with a size of m  r , where m is the number of compounds in query assigned to this gpu , is created in the global memory to store the computed tanimoto coefficient for each comparison .
the job of each comparison is similar to that on a single - gpu . after the comparison phase , on single - gpu ,
the result array is transferred from gpu to cpu ; on multi - gpus , the partial result arrays are transferred from gpus to cpu , respectively , and then these partial result arrays are merged into a complete result array . for each compound in query
, the compounds in database with more than 0.85 tanimoto coefficients are reported on cpu , respectively .
the threshold 0.85 in cuda - mcc is set up in order to report the compounds with the most ( possible ) similar structure .
it can be adjusted to report the results according to the requirements , even for complete results .
in this work , cuda - mcc was implemented by c+openmp+cuda . in order to evaluate cuda - mcc on single- and multi - gpus ,
the first machine has eight cpu cores ; each core is intel xeon e5 - 2670  cpu of 2.6  ghz and single nvidia tesla k20 m gpu card with 2496 core of each 0.71  ghz .
the second machine has eight cpu cores ; each core is intel xeon e5 - 2650  cpu of 2.0  ghz and dual - nvidia tesla k20 m gpu card .
there are three test sets used in the following tests : ( s1 ) ten thousand compounds in query and database , respectively , ( s2 ) thirty thousand compounds in query and database , respectively , and ( s3 ) fifty thousand compounds in query and database , respectively .
the first test is to evaluate cuda - mcc for these three test sets on single nvidia tesla k20 m gpu card in machines 1 and 2 . since the number of threads in a thread block will affect the performance by cuda - mcc , various numbers of threads in a thread block are used in the tests .
in addition , four lingo - based load - balancing strategies are also applied into these three test sets by considering the lingo score ( denoted by s ) , lingo number ( denoted by n ) , lingo length ( denoted by l ) , and lingo magnitude ( denoted by m ) .  
figure 3(a ) shows the speedup ratios of various numbers of threads in a thread block for these three test sets by cuda - mcc on single nvidia tesla k20 m gpu card in machine 1 .
the speedup ratios by cuda - mcc for four lingo - based load - balancing strategies in these three test sets on single nvidia tesla k20 m gpu card in machine 1 are shown in figure 3(b ) . in figure 3(a ) , the speedup ratio increases when the number of threads in a thread block increases .
overall , 1024 threads in a thread block have the best speedup ratios among three test sets , and cuda - mcc achieves 45 times faster than its cpu version on single nvidia tesla k20 m gpu card in machine 1 . in figure 3(b ) , cuda - mcc achieves more than 35 times faster than its cpu version on single nvidia tesla k20 m gpu card in machine 1 for three test sets by each load - balancing strategy .
the load - balancing strategies , s and m , outperform strategies l and n ; however , the difference between them is very small .
the performance and observations by cuda - mcc on single nvidia tesla k20 m gpu card in machine 2 are similar to those in machine 1 .
the second test is to evaluate cuda - mcc for these three test sets on dual - nvidia tesla k20 m gpu card in machine 2 .
the goals of this test are to demonstrate that cuda - mcc is useful for multi - gpus , and the speedup ratios can be improved by using multi - gpu cards .  
figure 4 shows the comparisons of speedup ratios by cuda - mcc on single nvidia tesla k20 m gpu card and dual - nvidia tesla k20 m gpu card in machine 2 for three test sets . from figure 4 ,
the speedup ratios by cuda - mcc on dual - nvidia tesla k20 m gpu card in machine 2 are significantly larger than those by cuda - mcc on single nvidia tesla k20 m gpu card in machine 2 .
cuda - mcc achieves 391 times faster than its cpu version on dual - nvidia tesla k20 m gpu card in machine 2 .
the execution time of cuda - mcc includes ( t1 ) the time of transferring structure arrays ( structure subarrays on multi - gpus ) from cpu to ( corresponding ) gpu in the comparison phase , ( t2 ) the time of comparing two sets of compounds in the comparison phase , ( t3 ) the time of transferring ( partial result arrays on multi - gpus ) result array from ( corresponding ) gpu to cpu in the output phase , and ( t4 ) the reporting ( and the time to merge partial result arrays into a complete result array on multi - gpus ) time to report the compounds with similar structure .
when running cuda - mcc on multi - gpus , both sizes of structure array in query and result array , needed to be transferred between cpu and one gpu , reduce .
in this paper , a gpu - based algorithm , cuda - mcc , was proposed and implemented to do the mcc problem on single- and multi - gpus .
four lingo - based load - balancing strategies were applied into cuda - mcc , and then discuss the effects by considering the lingo score , lingo number , lingo length , and lingo magnitude , respectively .
two machines with single nvidia tesla k20 m gpu card and dual - nvidia tesla k20 m gpu card were used to evaluate cuda - mcc , respectively . from experimental results ,
cuda - mcc achieved 45 times and 391 times faster than its cpu version on single nvidia tesla k20 m gpu card and dual - nvidia tesla k20 m gpu card , respectively .
two observations were summarized in this work : ( 1 ) the speedup ratio increases when the number of threads in a thread block increases and ( 2 ) the lingo score and lingo magnitude strategies outperform other two strategies . however , the difference between them is very small .
second , the benefits of estimating the computing workload by using these four lingo types are the same .
cuda - mcc is useful for o2a and a2a comparisons on single- and multi - gpus .
 compound comparison is an important task for the computational chemistry . by the comparison results , 
 potential inhibitors can be found and then used for the pharmacy experiments . 
 the time complexity of a pairwise compound comparison is o(n2 ) , where n is the maximal length of compounds . in general 
 , the length of compounds is tens to hundreds , and the computation time is small . 
 however , more and more compounds have been synthesized and extracted now , even more than tens of millions . 
 therefore , it still will be time - consuming when comparing with a large amount of compounds ( seen as a multiple compound comparison problem , abbreviated to mcc ) . 
 the intrinsic time complexity of mcc problem is o(k2n2 ) with k compounds of maximal length n. in this paper , we propose a gpu - based algorithm for mcc problem , called cuda - mcc , on single- and multi - gpus . 
 four lingo - based load - balancing strategies are considered in cuda - mcc in order to accelerate the computation speed among thread blocks on gpus . 
 cuda - mcc was implemented by c+openmp+cuda . 
 cuda - mcc achieved 45 times and 391 times faster than its cpu version on a single nvidia tesla k20 m gpu card and a dual - nvidia tesla k20 m gpu card , respectively , under the experimental results . 
1. Introduction
2. Background Knowledge
3. Method
4. Experiment Results
5. Conclusion