Amirali Sharifian edited subsection_Comparision_algorithm_For_comparing__.tex  over 8 years ago

Commit id: c26a58022a6e56909c776810754419c762cbbf56

deletions | additions      

       

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. Figure ... is the modified schema for comparing multiple reads with one reference. \\    \subsection{Computing Stride}  Using first 16 bits of a read and putting multiple reads in a one word processor even though it increases data level parallelism of our output but now for  each we need to figure out which read one  is a valid read and which one is not. In addition, even if we could figure out valid and non-valid reads from each other we will have memory fragmentation issue. Since we are not fetching our data consecutively and sometime we need to skip part of the memory. In this section we will describe our solutions for these two problem.\\ First, to figure outwhich read is  valid or not reads  we can use a secondary flags. secondary data.  For each read we use one flag bit telling current situation of the read and each time when we finish comparing, for instance, 16 bits of all reads we recompute flag bit to see whether the read is still valid. Figure ... shows added step to our previous algorithm.\\ Flag bits tell us what are the next reads we are going to copy to our word processor. There are two ways to fetch data into processor word, one way is each time when we are feeling the processor word first we can check flag of the read and decided whether we should copy it to our word processor or check the next flag. But then we have to do at least one additional comparing operation to decided. decide.  Another way is pre-computing readsthat  we need to fetch. We can use another secondary data structure telling us distance Suppose, we have stored reads in our memory and we just now beginning address  of the reads relative to in  the first read. memory.  We call it \emph{stride}. need additional information about our data so that we can load them into our word processor without checking flags. We know that we are going to fetch 16 bits for each read but the problem is that we don't know where should we begin.  Using stride flags in our previous part we can compute addresses we need to load our data from the memory. We use Fibonaci algorithm to compute distances from beginning address. Later, for loading data into our processor we just add distances to our beginning address and load correct  data structure into our word processor. We called these distances \emph{Strides}. Using strides  helps us to not checking flags each time we are trying to load our data and we just need to check flags once.  \subsection{Coding}