bsp_ex.cpp 12.5 KB
Newer Older
Davis King's avatar
Davis King committed
1
2
3
// The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt
/*

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    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 
Davis King's avatar
Davis King committed
19
           compiled bsp_ex.cpp program.  Let's call these window 1, window 2, and window 3.
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

        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.
Davis King's avatar
Davis King committed
38
39
40
41
42
43
*/





44
45
46
#include <dlib/cmd_line_parser.h>
#include <dlib/bsp.h>
#include <dlib/matrix.h>
Davis King's avatar
Davis King committed
47
48
49
50
51
52
53
54

#include <iostream>

using namespace std;
using namespace dlib;

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

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 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";
Davis King's avatar
Davis King committed
80
            parser.print_options(); 
81
82
83
84
85
86
87
88
89
90
            cout << endl;
            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);
Davis King's avatar
Davis King committed
91
92
            cout << "Listening on port " << listening_port << endl;

93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
            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));

Davis King's avatar
Davis King committed
134
            // bsp_connect() and bsp_listen() block until all the BSP nodes have terminated.
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
            // 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.
*/
Davis King's avatar
Davis King committed
154
double f (double x)
Davis King's avatar
Davis King committed
155
156
157
158
159
160
{
    return std::pow(x-2.0, 2.0);
}

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

161
void bsp_job_node_0 (bsp_context& bsp, double& min_value, double& optimal_x)
Davis King's avatar
Davis King committed
162
{
163
164
165
166
    // 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
Davis King's avatar
Davis King committed
167
    // number line subsequent iterations should focus on.  
168
169
170
171
172
173
174
175
    // 
    // 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. 


Davis King's avatar
Davis King committed
176
    // Now let's get down to work.  Recall that we are trying to find the x value that
177
178
    // 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
Davis King's avatar
Davis King committed
179
    // until it has located the minimizer of f(x) to within 1e-15 of its true value.
180
181
    double left = -1e100;
    double right = 1e100;
Davis King's avatar
Davis King committed
182
183
184
185

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

186
187
    // keep going until the window is smaller than 1e-15.
    while (right-left > 1e-15)
Davis King's avatar
Davis King committed
188
    {
189
190
191
192
193
194
195
196
197
198
        // 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 bsp_ex.cpp example program for an example.  
Davis King's avatar
Davis King committed
199
200
        bsp.broadcast(left);
        bsp.broadcast(right);
Davis King's avatar
Davis King committed
201

202
        // Receive the smallest values found from the other BSP nodes.
Davis King's avatar
Davis King committed
203
        for (unsigned int k = 1; k < bsp.number_of_nodes(); ++k)
Davis King's avatar
Davis King committed
204
        {
205
206
            // The other nodes will send std::pairs of x/f(x) values.  So that is what we
            // receive.
Davis King's avatar
Davis King committed
207
            std::pair<double,double> val;
Davis King's avatar
Davis King committed
208
            bsp.receive(val);
209
            // save the smallest result.
Davis King's avatar
Davis King committed
210
211
212
213
214
215
216
            if (val.second < min_value)
            {
                min_value = val.second;
                optimal_x = val.first;
            }
        }

217
        // Now narrow the search window by half.  
Davis King's avatar
Davis King committed
218
219
220
221
222
223
224
225
        interval_width *= 0.5;
        left  = optimal_x - interval_width/2;
        right = optimal_x + interval_width/2;
    }
}

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

226
void bsp_job_other_nodes (bsp_context& bsp, long grid_resolution)
Davis King's avatar
Davis King committed
227
{
228
229
230
231
    // 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.

Davis King's avatar
Davis King committed
232
    double left, right;
233
234
235
236
237
238
239

    // 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.  
    // 
Davis King's avatar
Davis King committed
240
    // Therefore, try_receive() serves both as a message receiving tool as well as an
241
242
243
244
245
246
    // implicit form of barrier synchronization.  In this case, we use it to know when to
    // terminate.  That is, we know it is the 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.  
Davis King's avatar
Davis King committed
247
    while (bsp.try_receive(left))
Davis King's avatar
Davis King committed
248
    {
Davis King's avatar
Davis King committed
249
        bsp.receive(right);
Davis King's avatar
Davis King committed
250

251
252
253
        // 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.
Davis King's avatar
Davis King committed
254
255
        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);
Davis King's avatar
Davis King committed
256
        const double width = right-left;
257
258
        // Select grid_resolution number of points which are linearly spaced throughout our
        // sub-window.
Davis King's avatar
Davis King committed
259
260
        const matrix<double> values_to_check = linspace(left+l*width, left+r*width, grid_resolution);

261
262
        // Search all the points in values_to_check and figure out which one gives the
        // minimum value of f().
Davis King's avatar
Davis King committed
263
        double best_x = 0;
Davis King's avatar
Davis King committed
264
265
266
267
268
269
270
271
272
273
274
        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);
            }
        }

275
276
277
        // 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.
Davis King's avatar
Davis King committed
278
        bsp.send(make_pair(best_x, best_val), 0);
Davis King's avatar
Davis King committed
279
280
281
282
283
    }
}

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