bsp_ex.cpp

// The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt
/*

    This is an example illustrating the use of the Bulk Synchronous Parallel (BSP)
    processing tools from the dlib C++ Library.  These tools allow you to easily setup a
    number of processes running on different computers which cooperate to compute some
    result.  

    In this example, we will use the BSP tools to find the minimizer of a simple function.  
    In particular, we will setup a nested grid search where different parts of the grid are
    searched in parallel by different processes.  


    To run this program you should do the following (supposing you want to use three BSP
    nodes to do the grid search and, to make things easy, you will run them all on your
    current computer):  

        1. Open three command windows and navigate each to the folder containing the 
           compiled bsp_ex.cpp program.  Let's call these window 1, window 2, and window 3.

        2. In window 1 execute this command:
             ./bsp_ex -l12345
           This will start a listening BSP node that listens on port 12345.  The BSP node
           won't do anything until we tell all the nodes to start running in step 4 below.

        3.  In window 2 execute this command:
             ./bsp_ex -l12346
           This starts another listening BSP node.  Note that since we are running this 
           example all on one computer you need to use different listening port numbers
           for each listening node.

        4. In window 3 execute this command:
             ./bsp_ex localhost:12345 localhost:12346
           This will start a BSP node that connects to the others and gets them all running.
           Additionally, as you will see when we go over the code below, it will also print
           the final output of the BSP process, which is the minimizer of our test function.
           Once it terminates, all the other BSP nodes will also automatically terminate.
*/





#include <dlib/cmd_line_parser.h>
#include <dlib/bsp.h>
#include <dlib/matrix.h>

#include <iostream>

using namespace std;
using namespace dlib;

// ----------------------------------------------------------------------------------------

// These are the functions executed by the BSP nodes.  They are defined below.
void bsp_job_node_0      (bsp_context& bsp, double& min_value, double& optimal_x);
void bsp_job_other_nodes (bsp_context& bsp, long grid_resolution);

// ----------------------------------------------------------------------------------------

int main(int argc, char** argv)
{
    try
    {
        // Use the dlib command_line_parser to parse the command line.  See the
        // compress_stream_ex.cpp example program for an introduction to the command line
        // parser.
        command_line_parser parser;
        parser.add_option("h","Display this help message.");
        parser.add_option("l","Run as a listening BSP node.",1);
        parser.parse(argc, argv);
        parser.check_option_arg_range("l", 1, 65535);


        // Print a help message if the user gives -h on the command line.
        if (parser.option("h"))
        {
            // display all the command line options
            cout << "Usage: bsp_ex (-l port | <list of hosts>)\n";
            parser.print_options(); 
            return 0;
        }


        // If the command line contained -l 
        if (parser.option("l"))
        {
            // Get the argument to -l
            const unsigned short listening_port = get_option(parser, "l", 0);
            cout << "Listening on port " << listening_port << endl;

            const long grid_resolution = 100;

            // bsp_listen() starts a listening BSP job.  This means that it will wait until
            // someone calls bsp_connect() and connects to it before it starts running.
            // However, once it starts it will call bsp_job_other_nodes() which will then
            // do all the real work.
            // 
            // The first argument is the port to listen on.  The second argument is the
            // function which it should run to do all the work.  The other arguments are
            // optional and allow you to pass values into the bsp_job_other_nodes()
            // routine.  In this case, we are passing the grid_resolution to
            // bsp_job_other_nodes().
            bsp_listen(listening_port, bsp_job_other_nodes, grid_resolution);
        }
        else
        {
            if (parser.number_of_arguments() == 0)
            {
                cout << "You must give some listening BSP nodes as arguments to this program!" << endl;
                return 0;
            }

            // Take the hostname:port strings from the command line and put them into the
            // vector of hosts.
            std::vector<network_address> hosts;
            for (unsigned long i = 0; i < parser.number_of_arguments(); ++i)
                hosts.push_back(parser[i]);

            double min_value, optimal_x;

            // Calling bsp_connect() does two things.  First, it tells all the BSP jobs
            // listed in the hosts vector to start running.  Second, it starts a locally
            // running BSP job that executes bsp_job_node_0() and passes it any arguments
            // listed after bsp_job_node_0.  So in this case it passes it the 3rd and 4th
            // arguments.  
            // 
            // Note also that we use dlib::ref() which causes these arguments to be passed
            // by reference.  This means that bsp_job_node_0() will be able to modify them
            // and we will see the results here in main() after bsp_connect() terminates.
            bsp_connect(hosts, bsp_job_node_0, dlib::ref(min_value), dlib::ref(optimal_x));

            // bsp_connect() and bsp_listen() block until all the BSP nodes have terminated.
            // Therefore, we won't get to this part of the code until the BSP processing
            // has finished.  But once we do we can print the results like so:
            cout << "optimal_x: "<< optimal_x << endl;
            cout << "min_value: "<< min_value << endl;
        }

    }
    catch (std::exception& e)
    {
        cout << "error in main(): " << e.what() << endl;
    }
}

// ----------------------------------------------------------------------------------------

/*
    We are going to use the BSP tools to find the minimum of f(x).  Note that
    it's minimizer is at x == 2.0.
*/
double f (double x)
{
    return std::pow(x-2.0, 2.0);
}

// ----------------------------------------------------------------------------------------

void bsp_job_node_0 (bsp_context& bsp, double& min_value, double& optimal_x)
{
    // This function is called by bsp_connect().  In general, any BSP node can do anything
    // you want.  However, in this example we use this node as a kind of controller for the
    // other nodes.  In particular, since we are doing a nested grid search, this node's
    // job will be to collect results from other nodes and then decide which part of the
    // number line subsequent iterations should focus on.  
    // 
    // Also, each BSP node has a node ID number.  You can determine it by calling
    // bsp.node_id().  However, the node spawned by a call to bsp_connect() always has a
    // node ID of 0 (hence the name of this function).  Additionally, all functions
    // executing a BSP task always take a bsp_context as their first argument.  This object
    // is the interface that allows BSP jobs to communicate with each other. 


    // Now let's get down to work.  Recall that we are trying to find the x value that
    // minimizes the f(x) defined above.  The grid search will start out by considering the
    // range [-1e100, 1e100] on the number line.  It will progressively narrow this window
    // until it has located the minimizer of f(x) to within 1e-15 of its true value.
    double left = -1e100;
    double right = 1e100;

    min_value = std::numeric_limits<double>::infinity();
    double interval_width = std::abs(right-left);

    // keep going until the window is smaller than 1e-15.
    while (right-left > 1e-15)
    {
        // At the start of each loop, we broadcast the current window to all the other BSP
        // nodes.  They will each search a separate part of the window and then report back
        // the smallest values they found in their respective sub-windows.  
        // 
        // Also, you can send/broadcast/receive anything that has global serialize() and
        // deserialize() routines defined for it.  Dlib comes with serialization functions
        // for a lot of types by default, so we don't have to define anything for this
        // example program.  However, if you want to send an object you defined then you
        // will need to write your own serialization functions.  See the documentation for
        // dlib's serialize() routine or the bridge_ex.cpp example program for an example.  
        bsp.broadcast(left);
        bsp.broadcast(right);

        // Receive the smallest values found from the other BSP nodes.
        for (unsigned int k = 1; k < bsp.number_of_nodes(); ++k)
        {
            // The other nodes will send std::pairs of x/f(x) values.  So that is what we
            // receive.
            std::pair<double,double> val;
            bsp.receive(val);
            // save the smallest result.
            if (val.second < min_value)
            {
                min_value = val.second;
                optimal_x = val.first;
            }
        }

        // Now narrow the search window by half.  
        interval_width *= 0.5;
        left  = optimal_x - interval_width/2;
        right = optimal_x + interval_width/2;
    }
}

// ----------------------------------------------------------------------------------------

void bsp_job_other_nodes (bsp_context& bsp, long grid_resolution)
{
    // This is the BSP job called by bsp_listen().  In these jobs we will receive window
    // ranges from the controller node, search our sub-window, and then report back the
    // location of the best x value we found.

    double left, right;

    // The try_receive() function will either return true with the next message or return
    // false if there aren't any more messages in flight between nodes and all other BSP
    // nodes are blocked on calls to receive or have terminated.  That is, try_receive()
    // only returns false if waiting for a message would result in all the BSP nodes
    // waiting forever.  
    // 
    // Therefore, try_receive() serves both as a message receiving tool as well as an
    // implicit form of barrier synchronization.  In this case, we use it to know when to
    // terminate.  That is, we know it is time to terminate if all the messages between
    // nodes have been received and all nodes are inactive due to either termination or
    // being blocked on a receive call.  This will happen once the controller node above
    // terminates since it will result in all the other nodes inevitably becoming blocked
    // on this try_receive() line with no messages to process.  
    while (bsp.try_receive(left))
    {
        bsp.receive(right);

        // Compute a sub-window range for us to search.  We use our node's ID value and the
        // total number of nodes to select a subset of the [left, right] window.  We will
        // store the grid points from our sub-window in values_to_check.
        const double l = (bsp.node_id()-1)/(bsp.number_of_nodes()-1.0);
        const double r = bsp.node_id()    /(bsp.number_of_nodes()-1.0);
        const double width = right-left;
        // Select grid_resolution number of points which are linearly spaced throughout our
        // sub-window.
        const matrix<double> values_to_check = linspace(left+l*width, left+r*width, grid_resolution);

        // Search all the points in values_to_check and figure out which one gives the
        // minimum value of f().
        double best_x = 0;
        double best_val = std::numeric_limits<double>::infinity();
        for (long j = 0; j < values_to_check.size(); ++j)
        {
            double temp = f(values_to_check(j));
            if (temp < best_val)
            {
                best_val = temp;
                best_x = values_to_check(j);
            }
        }

        // Report back the identity of the best point we found in our sub-window.  Note
        // that the second argument to send(), the 0, is the node ID to send to.  In this
        // case we send our results back to the controller node.
        bsp.send(make_pair(best_x, best_val), 0);
    }
}

// ----------------------------------------------------------------------------------------