Merging upstream version 1.45.3+dfsg.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 282 insertions, 0 deletions

diff --git a/src/ml/dlib/examples/bsp_ex.cpp b/src/ml/dlib/examples/bsp_ex.cpp
new file mode 100644
index 000000000..7dffa68d6
--- /dev/null
+++ b/src/ml/dlib/examples/bsp_ex.cpp
@@ -0,0 +1,282 @@
+// 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);
+    }
+}
+
+// ----------------------------------------------------------------------------------------
+