Jump to content


Check out our Community Blogs

kmhosny

Member Since 18 Feb 2008
Offline Last Active Jan 10 2011 02:21 PM
-----

Topics I've Started

Problem in MPI with C

13 April 2010 - 03:07 AM

Hi all,
i am trying to write an parallel program that read a file and search for a word within this file.
the word is given by the user as a console input.
now the problem is when i add MPI APIs to the code it acts in a weird manner for instance i print "enter word" to the user and then take the input with MPI it goes the other way it takes the input then prints.
also when i try to run more than one process they all run in the same console window !!!
here is my code:
// Parallel_MPI_Assignment_1.cpp : Defines the entry point for the console application.
//
#include "mpi.h"
#include<cstring>
#include<cstdlib>
int main(int argc, char* argv[])
{
    
    MPI_Init(&argc,&argv);
    int rank;
    int length=50,size=0;
    long file_size=0;
    char* search_word=(char*)malloc(length);    

    memset(search_word,0,sizeof(search_word));
    MPI_Comm_rank( MPI_COMM_WORLD, &rank );
    printf("I Am :%d\n",rank);
    
    if(rank==0)
    {
        printf("please enter the word to search -make sure its less than 49-: ");
    
        scanf("%s",search_word);
        size=strlen(search_word);
        search_word[49]='\0';
        printf("%s\n",search_word);
    }
    
    
    
    free(search_word);
    MPI_Finalize();
    return 0;
}
i am using VS 2005


Using loop to traverse tree

29 March 2010 - 12:10 PM

Hi All,
What i am going to write about is using loops to traverse trees instead of using the basic recursion technique.
The recursion technique is indeed a good method when traversing a medium size tree but most probably it may end with a buffer overflow exception if the tree is large enough.
A quick review on what happens when you use recursion:

when using recursion the program operates ordinary as the same way in a function call, since recursion is indeed a function call.

what happens is that each cycle the program calls the function, the program counter is pushed to indicate the line it stopped at before calling this function and the activation record for that function is pushed onto the program stack where the activation record contains the function local variables and addresses.

when the function terminates, the activation record of the function is removed form the top of the stack and the program counter is read and the program continues executing from the first line after the function call.

now imagine it with recursion where in each call the function is pushed onto the stack and then pushed again and again and again the memory allocated may increase in a high speed and gets fulled and overflows and that may occur frequently when traversing a large tree.
The Loop way:

So the alternative is to use loops that simulates what does happen when recursion is called.

basically what i am going to do is to create a stack of the node type and push on it first the root node, then i am going to pop the node and push it's children and next cycle pop the node and push it's children and so on till the stack is emptied and my looping condition will be loop if the stack size is > 0.

Example:
#include<iostream>
#include<stack>
using namespace std;

#define NULL 0
class Node
{
public:
    Node* left;
    Node* right;
    int id;
    Node()
    {
        left=NULL;
        right=NULL;
        id=0;

    }
};
void traverse_tree_loop(Node n)
{
    stack<Node> tree;
    tree.push(n);
    while(tree.size()>0)
    {
        Node temp=tree.top();
        tree.pop();
        cout<<"i am ID#: "<<temp.id<<endl;
        if(temp.right!=NULL)
            tree.push(*(temp.right));
        if(temp.left!=NULL)
            tree.push(*(temp.left));
    }
}
 int main()
{
    Node root;
    Node ch1;
    Node ch2;
    Node ch3;
    Node ch4;
    Node ch5;
    root.id=0;
    root.left=&ch1;
    root.right=&ch2;
    ch1.id=1;
    ch1.left=&ch3;
    ch1.right=&ch4;
    ch2.id=2;
    ch2.left=&ch5;
    ch3.id=3;
    ch4.id=4;
    ch5.id=5;
    traverse_tree_loop(root);
    return 1;
}

the tree is:
0-as root with left child 1, right child 2
1 has child 3 as left, child 4 as right
2 has child 5 as left child.
the output for this program is:
i am ID#: 0
i am ID#: 1
i am ID#: 3
i am ID#: 4
i am ID#: 2
i am ID#: 5

So by this basic tutorial we can see that trees can be traversed using loops in an easy way which is simulating what happens in the recursion way.
Thank you for reading and i hope i was helpful.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download