[Networkit] new core decomposition algorithm

Henning Meyerhenke henning.meyerhenke at kit.edu
Thu Sep 17 14:51:29 CEST 2015


Some additional measurements on phipute1 show that the new 
implementation with Max's thread local buffers is clearly faster (a 
factor of 5 is typical) than the old one. I will switch the default to 
the new one again (for permissible settings).

Best,
Henning



[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[BEGIN] reading graph G(n=862664, m=16138468) from METIS file: eu-2005
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/eu-2005.metis.graph: (184 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/eu-2005.metis.graph: (1100 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=540486, m=15245729) from METIS file: coPapersDBLP
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/coPapersDBLP.metis.graph: 
(178 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/coPapersDBLP.metis.graph: 
(729 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=18520486, m=261787258) from METIS file: uk-2002
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/uk-2002.metis.graph: (4785 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/uk-2002.metis.graph: (21513 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=50912018, m=54054660) from METIS file: europe-osm
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/europe-osm.metis.graph: 
(1244 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/europe-osm.metis.graph: 
(11606 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=5154859, m=47022346) from METIS file: cage15
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/cage15.metis.graph: (196 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/cage15.metis.graph: (4211 ms)
[       OK ] CentralityGTest.benchCoreDecompositionDimacsGraphs (117323 ms)
[
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=862664, m=16138468) from METIS file: eu-2005
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/eu-2005.metis.graph: (181 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/eu-2005.metis.graph: (1084 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=540486, m=15245729) from METIS file: coPapersDBLP
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/coPapersDBLP.metis.graph: 
(138 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/coPapersDBLP.metis.graph: 
(732 ms)
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 44: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:


[BEGIN] reading graph G(n=18520486, m=261787258) from METIS file: uk-2002
[INFO ][“networkit/cpp/io/METISGraphReader.cpp”, 107: virtual 
NetworKit::Graph NetworKit::METISGraphReader::read(const string&)]:
[DONE]
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 624: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for ParK of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/uk-2002.metis.graph: (4783 ms)
[INFO ][“networkit/cpp/centrality/test/CentralityGTest.cpp”, 630: 
virtual void 
NetworKit::CentralityGTest_benchCoreDecompositionDimacsGraphs_Test::TestBody()]: 
Time for bucket queue based k-core decomposition of 
/home/i11/staudt/Graphs/Static/DIMACS/Large/uk-2002.metis.graph: (21686 ms)





Am 17.09.15 um 10:35 schrieb Maximilian Vogel:
>
>> But clearly, it must be found out what hampers the ParK implementation
>> (and if this is due to the algorithm or the implementation).
> In the paper it is stated, that the atomicIncrement operations realized
> with the omp atomic capture statement are carried out in batches of
> sizes of at least one cache line. Therefore, thread local buffers are
> needed. I've pushed some changes where each thread in the loops in
> parallelScan and processSublevelParallel has a vector to push nodes to.
> These vectors are combined in the end of the function. Thus, only one
> omp atomic capture statement remains. Here are results from phipute:
>
> graph G(n=862664, m=16138468) from METIS file: eu-2005
> Time for ParK of
> /algoDaten/staudt/Graphs/Collections/ICPP/L/eu-2005.metis.graph: (280 ms)
> Time for bucket queue based k-core decomposition of
> /algoDaten/staudt/Graphs/Collections/ICPP/L/eu-2005.metis.graph: (1118 ms)
>
> graph G(n=18520486, m=261787258) from METIS file: uk-2002
> Time for ParK of
> /algoDaten/staudt/Graphs/Collections/ICPP/L/uk-2002.metis.graph: (4773 ms)
> Time for bucket queue based k-core decomposition of
> /algoDaten/staudt/Graphs/Collections/ICPP/L/uk-2002.metis.graph: (22349 ms)
>
> Note that this is not the same eu-2005 graph Christian used.
>
> There are still a few issues with the implementation:
> - the scan-function (both implementations) scans over all nodes in each
> iteration. If the implementation kept the "alive"-information for nodes,
> this could be reduced.
> - it should be possible to remove the remaining omp atomic capture
> statement, but I'm not yet sure whether this will increase the performance.
>
>
> Best,
> Max
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>

-- 

=======================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
=======================================================

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150917/10bd6468/attachment.p7s>


More information about the NetworKit mailing list