weekly report 9 – Barış Akşanlı
Lastly, we decided to construct a new algorithm in order to achieve a better performance in parallelism. To do this, we need to ensure the independence between the blocks in order not to deal with any block synchronization issue. This algorithm works as:
- First we determine a level in which there are at least 30 gates. This number then will be used as block number. (This determination is generic, in other words, we can change it to 40 or 50 to see if increased number of blocks will result in better performance)
- After determining the relevant level, we start going back from each of the and gates in that level and construct a triangular shape.
- In the base of that triangle, there are the inputs and in the rightest part there is the single output.
- When determining this triangular shape, we copy the necessary gates for each block, so that the blocks become independent from each other.
- We try to leave the number of gates coming after the determined level low so that they can be simulated by just one block. (If we did not ensure this, we would again need to deal with explicit block synchronization which does not operate correctly every time.)
- After implementing this algorithm we started to make some time efficiency control. At the beginning the method worked quite inefficient(slower than the sequential version). However, after this observation, we started to use the techniques that CUDA offers us. Those include mostly memory optimizations.
- We should make the need for global memory as less as possible since reaching to device global memory is a quite expensive operation. We traced our code and made optimizations based on this phenomenon. Then, we observed an increase in time efficiency. However, the level is still not as good as we expect.
Next Goal: During the next week we will work on optimizing this method further since this method promises more ways for optimization. And we also begin to use the test cases coming from sparc and opencore.
Barış Akşanlı
