Parallelizing Transition fault testing algorithm

Hi,

I am working towards parallelization of one of my own sequential program. The sequential program is used to generate test patterns for Delay testing. (Testing of the rise and fall delays in a circuit). It takes up a lot of time to run and is a massively parallel program. So parallelization is a good idea to achieve speed up. I gathered a few points on parallelization of the program from the book "Parallel programming for Multicore and cluster systems" by Thomas Rauber Gudula Runger, I present them here.

Aim: To parallelize the transition fault testing program so that it runs on more than one processor

Steps involved in parallelization

1. Decomposition of the computations :
GOAL : of task decomposition is keeping all the processors busy at all times.

a. Computations of the sequential algorithm are decomposed into tasks and dependencies between the tasks are determined.Tasks are the smallest units of parallelism.

b. Task may involve accesses to shared address space or may execute message passing operations


GRANULARITY :  computation time of a task. must take this into consideration when dividing the work into tasks. the granularity must be long enough to compensate for the scheduling overheads.

The decomposition step must find a good compromise between the number of tasks and their granularity.

2. ASSIGNMENT OF TASKS TO PROCESSES OR THREADS
GOAL: partition the tasks to achieve good load balancing results.

a. The flow of control executed by a single processor is a process or a thread
usually the number of processes or threads is the same as the number of cores.

b. To take into consideration, the number of memory accesses or communication operation for data exchange. EX- assign two tasks which work on the same data set to the same thread since this leads to a good cache usage.

c. SCHEDULING : the assignment of tasks to processes or threads is scheduling.
    static scheduling
    dynamic scheduling

3. Mapping of processes or threads to physical cores - mapping can be done by the operating systems supported by program statements. The main goal is get an equal utilization of the processors or cores while keeping communication between the processors as small as possible.

Next step is to analyze the program so as to implement the steps and make a detailed documentation. A job which is started properly is half done :)

Abishek Ramdas
NYU Poly

Comments

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