Amirali Sharifian edited subsection_Comparision_algorithm_For_comparing__.tex  over 8 years ago

Commit id: ea81a0e4a9b037f13af1648112b247fc427e05ba

deletions | additions      

       

  Now number of operations we are doing to comparing reads with a reference would be depend on the size of our word processor. In modern CPUs $w$ is usually 32 or 64 (and if we use SIMD operations our register's length can be 128 or more). For instance if our word processor length is equal to 64 and our read's length is 100 then first segment would contain $64\%$ of our read. In other words we still using big portion of reads to determine should we continue our comparison procedure or should we stop since even in the first $64\%$ number of errors exceed \emph{e}. According to Figure ... using first $64\%$ of each reads can filter out nearly .... of our data with comparing just first segment.\\  But what if we can answer this question with even less comparison. For instance what if we use only first 16 bps of our read and compare it with the reference. Figure ... shows that number of reads going to filter won't change significantly and the number would stay the same. However, if we use first 16bps we will have more segments and as a result number of operation we should do for rest of our reads will increase but since we can filter out more data it will still have positive effect on our performance.\\  Now if we get same result from comparing 16 first bits in compare with first 32 bits then we can reduce number of bits transferring with just using 16 bits. Suppose our word processor length is equal to 32s but we just need 16 bits, as a result we are not using 16bits of our processor. But we can increase instruction level parallelism with interleaving different reads and instead of loading one read into each word processor we can now load two reads and process them together. Consequitively, our parallelism will limit to our word processor length. If we can provide bigger processor word (like SIMD registers)  we can process more reads in a same time.\\  Using interleaving technique would result changes in our storage layout. time. Figure ... is the modified schema for comparing multiple reads with one reference. \\