[Networkit] new core decomposition algorithm

Henning Meyerhenke henning.meyerhenke at kit.edu
Thu Sep 17 10:46:37 CEST 2015


Max,

Great, thanks!

NB: I've asked the ParK authors if they are willing to open their code. 
That may give additional insights.

Scanning fewer nodes is indeed a possible approach for further 
acceleration. Sequentially this is relatively easy (but requires a 
deviation from the parallelizable code structure), but in parallel (our 
focus) it needs more thought.

Best,
Henning


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/76d28240/attachment-0001.p7s>


More information about the NetworKit mailing list