Parallelization of SOBOL Quasi Random Number Generator

Sobol Quasi Random Number Generaotors

Sobol Quasi Random Number Generaotors (sobol QRNG) are pseudo random number generators. There are often applications, for example in financial engineering, where random numbers are to be generated within an upper and lower limit. The main requirement of the random numbers to be generated in these applications are that the random numbers must fill the N space more uniformly than uncorrelated random points.

The serial algorithm for Sobol QRNG can be found at
"Implementation of Sobol Quasi Random Number generator “sobseq()” Chapter 7.7, Numerical Recepies in C, http://www.nrbook.com/a/bookcpdf.php"

I have used pthreads to parallelize the algorithm. The main idea is "Divide and Conquer". If 64000 patterns are to be generated by 4 threads then each thread generates 64000/4 = 16000 random numbers.

The catch is that each thread must be provided with an intial seed so that no two threads generate the same set of random numbers. How do u generate the seed? That is another big story.

Below you can find my detailed report on parallelizing the pseudo random number generator using pthreads.

Detailed Report :  Sobol QRNG parallelized version.
 
https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B4rJ5uMNHA9pZTA0MjI3YjYtOTgzYi00M2ZhLTk3NDUtOGNiMGQ2MmQ4M2Vh&hl=en&authkey=CPypsogJ

Useful References:
1.ALGORITHM 659 Implementing Sobol’s Quasirandom Sequence Generator PAUL BRATLEY and BENNETT L. FOX Universite de Montrkal .
2.Implementation of Sobol Quasi Random Number generator “sobseq()” Chapter 7.7, Numerical Recepies in C, http://www.nrbook.com/a/bookcpdf.php
3.“A primer for Monte Carlo method by Sobol” 1994 CRC Press.Inc, ISBN 0-8493-8673-X.
4.Quasirandom Number Generators for Parallel Monte Carlo Algorithms , B. C. BROMLEY , 38,101–104 (1996) JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING.
5.Posix Threads Programming Tutorial, https://computing.llnl.gov/tutorials/pthreads/
6.Normalized distributions, Wikipedia, http://en.wikipedia.org/wiki/Normal_distribution
7.Gray Code, Wikipedia, http://en.wikipedia.org/wiki/Gray_code


It had been a good experience for me getting the feel of parallel programming. Save a few bugs, the program is running fine. Need to resolve the bugs asap :)
I feel good.

Comments

  1. UnknownJanuary 4, 2015 at 10:17 PM

    Good article.Thanks for your sharing,i learn a lot from your post.There is a lot of very useful knowledge in your post.I enjoy reading it and hope to see more.Can you write more about this topic?I am very interested in it.Waiting for your new post.
    draw barcode within java

    ReplyDelete

Post a Comment

Popular posts from this blog

Setting up atalanta ATPG to work on Linux

Atalanta is an ATPG tool that is used to generate test patterns for combinational circuits. atalanta is a windows executable file. I am using Atalanta ATPG tool to generate the test patterns required for generating the Transition fault Test patterns RUNNING ATALANTA (LINUX) You need to have WINE installed to run windows executable binary. Created a symbolic link in the usr/bin to the atalanta.exe, name of the link s atalanta. (not necessary if you do not have root privilages) chmod u+x /place/atalanta/atalanta.exe cd /usr/bin sudo ln -s /place/atalanta/atalanta.exe ./atalanta COMMAND TO RUN ATALANTA atalanta [option] filename //put this in a shell script
Read more

Generating 16k ROM using Xilinx IP COREGEN and simulating it in modelsim

The instruction ROM is an IP Core. so before interfacing with the open8, it has to be generated. The method of generating and simulating a ROM Xilinx IP Core is described here. FIND ALL THE FILES HERE 1. app.coe (the initialization file) 2. rom_16k_core.vhd 3. rom_16k_core.vho 4. rom_16k_core.xco 5. top_level.vhd 6. do_memgen.do Creation of the ROM Xilinx 10.1 1. open ISE 2. create a new project 3. tools -> core generator(12.1) (or right click on the device and add a new file 10.1) 4. In the IP catalog -> Memory and storage elements -> RAM and ROM 5. double click on block memory generator, A new window opens 6. In the new window select single port ROM click next, Write first mode 7. Select Read Width = 8 and Read Depth = 16384 for 16K ROM -> next 8. The output ports are unregistered, load initialization COE if required -> next 9. No need to use the Reset pin -> next 10. Generate. (takes a little time then shows successfully generated) This
Read more

Sparse matrix - 3 tuple representation

//program to 3-tuple representation #include<stdio.h> #include<unistd.h> #define SIZE 3000; void main() { int a[5][5],row,columns,i,j; printf("Enter the order of the matrix(5*5)"); scanf("%d %d",&row,&columns); printf("Enter the element of the matrix\n"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { scanf("%d", &a[i][j]); } printf("3-tuple representation"); for(i=0;i<row;i++) for(j=0;j<columns;j++) { if(a[i][j]!=0) { printf("%d %d %d", (i+1),(j+1),a[i][j]); } } getchar(); }
Read more