Basic Toolchain for Partitioning by MoKob · Pull Request #3603 · Project-OSRM/osrm-backend

MoKob · 2017-01-23T14:42:14Z

Builds basic infrastructure outline in #3586, defining interfaces and connections between the different parts. Foundation for #3205.

Tasks

Once done

review
adjust for comments

daniel-j-h · 2017-01-24T17:06:28Z

include/partition/bisection_graph.hpp

+        ++node_id;
+
+        return {static_cast<std::size_t>(std::distance(edges.begin(), edges_of_node)), coordinate};
+    };


Hm can we clean this one up - the stateful lambda with init captures and transform is a bit ugly

daniel-j-h · 2017-01-24T17:09:24Z

include/partition/inertial_flow.hpp

+  public:
+    InertialFlow(const GraphView &view);
+
+    std::vector<bool> ComputePartition(const double balance, const double source_sink_rate);


Should we use dynamic bitset here

http://www.boost.org/doc/libs/1_63_0/libs/dynamic_bitset/dynamic_bitset.html

(search for vector bool in the docs there)

What do you mean with balance and source sink rate here?

If balance is 0.25 we take 0.25 * nodes as source and 0.25 * nodes as sinks, right?

Also seeing you implemented the skeleton as stateful class holding a graph view ref. I suppose you want to abstract the try-n-cuts-take-best inside ComputePartition (?)

The interface here is just a placeholder for me to imagine what would happen:

balance would be a guideline for the cuts to be chosen. Any flow that is computed gives a large number of possible cuts (e.g. a-b-c-d-e-f-g-h can be split on any intermediate node with an identical cut size). The balance would guide the flow algorithm which of the possible minimal flows to report / what kind of effort to spend on balancing the cuts in size

the source/sink-rate would be for the initialisation of the flow algorithm. The inertial flow picks X percent of the nodes as source/sink, right? So that would be the X.

For the statefulness: we can easily make this not stateful and make the flow algorithm do the best out of n part here. That was just to get something working quickly to iterate on.

daniel-j-h · 2017-01-24T17:12:58Z

include/partition/partition_config.hpp

+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


License can go

* Implements Random Access Iterator Facade for EdgeIDIterator * Makes StaticGraph Node and Edge requirements explicit * Cleans up Bisection Graph, Node and Edge * Cleans up GraphView

daniel-j-h · 2017-01-25T10:50:50Z

include/partition/graph_view.hpp

    void advance(difference_type offset) { position += offset; }
    bool equal(const EdgeIDIterator &other) const { return position == other.position; }
-    const reference dereference() const { return position; }
+    reference dereference() const { return position; }


Hm why the change here?

since reference is already const due to https://github.com/Project-OSRM/osrm-backend/pull/3603/files/50b03a93f9472a3e726fc82d6d452ecb1561054f..3bde4426d491540190d403b889f5a8fcf702164a#diff-d79e8547c1b4e3f383ca1879d7db6bebL35 and my compiler complained about the double const

* Implements Random Access Iterator Facade for EdgeIDIterator * Makes StaticGraph Node and Edge requirements explicit * Cleans up Bisection Graph, Node and Edge * Cleans up GraphView

daniel-j-h · 2017-01-31T15:59:50Z

src/tools/extract.cpp

+        boost::program_options::value<bool>(&extractor_config.dump_compressed_node_based_graph)
+            ->implicit_value(true)
+            ->default_value(false),
+        "Generate a partitionable graph file (.cnbg) for use with osrm-partition")(


Hm on the demo server with Boost 1.55 I have to say --dump-partition-graph true even though implicit_value above should only require dump-partition-graph. No idea if this is an Boost issue...

http://www.boost.org/doc/libs/1_55_0/doc/html/boost/program_options/typed_value.html#idp101668472-bb

Can we just do -DENABLE_MASON=ON on the demoserver and pretend this is ancient history?

It works specifying it explicitly.

* Implements Random Access Iterator Facade for EdgeIDIterator * Makes StaticGraph Node and Edge requirements explicit * Cleans up Bisection Graph, Node and Edge * Cleans up GraphView

…ilation bug

Here's all I could get out of a instrumented `osrm-partition`; debug build, with all the bells and whistles I could think of to make it more verbose: ``` ==17928==ERROR: LeakSanitizer: detected memory leaks Direct leak of 1560 byte(s) in 3 object(s) allocated from: #0 0x7f4244185b30 in operator new[](unsigned long) ../../../../libsanitizer/asan/asan_new_delete.cc:62 #1 0x7f4242a788b3 (/usr/lib/libtbb.so.2+0x208b3) SUMMARY: AddressSanitizer: 1560 byte(s) leaked in 3 allocation(s).<Paste> `` Symbolizing the address results in ``` echo "/usr/lib/libtbb.so 0x7f4242a788b3" | llvm-symbolizer _fini ``` Looks like a crt finalizer => static global dtor "leaking" from tbb. Which turned out to be a missing `tbb::task_scheduler_init` on our end: > Using task_scheduler_init is optional in Intel® Threading Building > Blocks (Intel® TBB) 2.2. By default, Intel TBB 2.2 automatically creates > a task scheduler the first time that a thread uses task scheduling > services and destroys it when the last such thread exits. https://www.threadingbuildingblocks.org/docs/help/hh_goto.htm?index.htm#reference/task_scheduler/task_scheduler_init_cls.html Without an explicit instanz the first call to a tbb algorithm seem to initialize a global scheduler singleton which then "leaks" until the program exits. Phew.

…ition

fix windows compilation no multi line warnings sanitze on mason with newer TBB

TheMarex · 2017-03-01T00:15:25Z

Grabbing this PR for rebasing and fixing PR comments.

* Implements Random Access Iterator Facade for EdgeIDIterator * Makes StaticGraph Node and Edge requirements explicit * Cleans up Bisection Graph, Node and Edge * Cleans up GraphView

MoKob added MLD Work In Progress labels Jan 23, 2017

daniel-j-h mentioned this pull request Jan 24, 2017

Partitioner Improvements and Utils on top of #3603 #3611

Merged

daniel-j-h reviewed Jan 24, 2017

View reviewed changes

MoKob force-pushed the tools/partitionining/graph_view branch from 842bd66 to 50b03a9 Compare January 25, 2017 10:09

daniel-j-h reviewed Jan 25, 2017

View reviewed changes

daniel-j-h mentioned this pull request Jan 25, 2017

Spatial Order + Rotating Slope for #3603 #3612

Merged

MoKob force-pushed the tools/partitionining/graph_view branch 2 times, most recently from 1561fb1 to 6518d17 Compare January 26, 2017 12:40

MoKob force-pushed the tools/partitionining/graph_view branch from 02502d3 to 6b64487 Compare January 27, 2017 10:26

daniel-j-h mentioned this pull request Jan 27, 2017

Implements Compressed Node Based Graph (De-)Serialization #3620

Closed

1 task

daniel-j-h reviewed Jan 31, 2017

View reviewed changes

MoKob force-pushed the tools/partitionining/graph_view branch from 1876ba5 to fd939a6 Compare February 1, 2017 09:50

This was referenced Feb 1, 2017

Calculating Flows Recursively #3586

Closed

Implements Recursively Descending the Bisection Tree in Parallel #3637

Merged

daniel-j-h changed the title ~~Basic Toolchain for OSRM partition~~ Basic Toolchain for Partitioning Feb 1, 2017

This was referenced Feb 1, 2017

Implement Dummy Partitioner #3204

Closed

Pulls parameters through to make them configurable from the outside #3639

Merged

Unit Tests for Partitioner #3643

Closed

MoKob force-pushed the tools/partitionining/graph_view branch from 90a4cbf to 9d62e4f Compare February 2, 2017 13:17

MoKob force-pushed the tools/partitionining/graph_view branch from 9d62e4f to 079611f Compare February 2, 2017 13:19

daniel-j-h mentioned this pull request Feb 2, 2017

Implements Mapping for NodeBasedGraph -> EdgeBasedGraph Translation #3645

Merged

Moritz Kobitzsch and others added 20 commits March 1, 2017 00:14

add unit tests for the different components of the parttion tool

f33dafa

Dump memory usage stats after partitioning.

5de46ac

Be -fpermissive with gcc49: required for tbb::parallel_do_feeder comp…

0fa9162

…ilation bug

generate stats in annotation

4403608

Installs osrm-partition tool and library

4acf79a

Implements Mapping for NodeBasedGraph -> EdgeBasedgraph Translation

f53a1fd

Split Partitioner I/O off into separate headers

f7d6952

Loads the edge based graph edges and constructs a dynamic graph from it

57852af

First try at artificial nodes

f305ccc

Store flag for artificial bounary edges and walk border nodes in ebg

64d5a4b

Sigh. Just randomly pick a side for border nodes for now..

b26c044

Re-use the extractor edge based edge for loading the ebg in osrm-part…

b2db1ae

…ition

fix edge duration truncation in partition, pending global fix

dc46d22

fix windows compilation no multi line warnings sanitze on mason with newer TBB

fix tbb leaks

5cb25a5

don't check for files not actually read

372bbd4

adjust cell_storage tests to new StaticGraph interface

317a9fd

adjust extractor scc to new StaticGraph

f98b099

fixed warnings

a5fc4d2

return vector with correct edges

d397c3e

TheMarex force-pushed the tools/partitionining/graph_view branch from 8c7e79c to 6759982 Compare March 1, 2017 00:49

TheMarex added 2 commits March 1, 2017 01:03

Make InertialFlow a function

fd39a3c

Fix help texts and .nbg_to_ebg -> .cnbg_to_ebg

6f34d70

TheMarex force-pushed the tools/partitionining/graph_view branch from 6759982 to 6f34d70 Compare March 1, 2017 01:04

TheMarex added Ready To Merge and removed Review - In feedback labels Mar 1, 2017

TheMarex merged commit 886421b into master Mar 1, 2017

TheMarex deleted the tools/partitionining/graph_view branch March 1, 2017 16:09

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Basic Toolchain for Partitioning#3603

Basic Toolchain for Partitioning#3603
TheMarex merged 30 commits intomasterfrom
tools/partitionining/graph_view

MoKob commented Jan 23, 2017 •

edited

Loading

Uh oh!

daniel-j-h Jan 24, 2017

Uh oh!

daniel-j-h Jan 24, 2017

Uh oh!

daniel-j-h Jan 24, 2017

Uh oh!

daniel-j-h Jan 24, 2017

Uh oh!

MoKob Jan 25, 2017

Uh oh!

daniel-j-h Jan 24, 2017

Uh oh!

daniel-j-h Jan 25, 2017

Uh oh!

MoKob Jan 25, 2017

Uh oh!

daniel-j-h Jan 31, 2017

Uh oh!

danpat Jan 31, 2017

Uh oh!

daniel-j-h Feb 1, 2017

Uh oh!

TheMarex commented Mar 1, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

Uh oh!

Conversation

MoKob commented Jan 23, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Once done

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

TheMarex commented Mar 1, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

MoKob commented Jan 23, 2017 •

edited

Loading