Skip to content

Releases: mbuzdalov/non-dominated-sorting

v0.2.1: The first version on Maven Central

27 Nov 15:44
@mbuzdalov mbuzdalov
v0.2.1
ab3622c
Compare
Choose a tag to compare
v0.2.1: The first version on Maven Central Latest
Latest

This is the short list of changes since version 0.2:

  • Filter Sort is implemented.
  • Set Intersection Sort, aka "merge non-dominated sorting", is implemented.
  • Implementation of Sumit Mishra's DNCS was significantly improved.
  • Lots of small improvements to the commonly used subroutines.
Assets 2
Loading

v0.3: 2nd year report for Russian Science Foundation

29 May 17:01
@mbuzdalov mbuzdalov
v0.3
025dfe1
Compare
Choose a tag to compare
v0.3: 2nd year report for Russian Science Foundation Pre-release
Pre-release

This release features two components.

A report on speed-ups in parallel non-dominated sorting.

On input sizes of 1000000 the divide-and-conquer algorithm, hybridized with ENS-SS, is able to achieve a speed-up of 4.44 with 8 threads.

The same algorithm hybridized with ENS-NDT, due to a higher threshold value, is not that good in parallelization: the maximum speed-up observed below is 2.721 with 8 threads.

The general trend is that the possible speed-ups increase with both the number of points and the dimension. Due to the divide-and-conquer algorithm structure, there is no parallelization available for dimensions 2 and 3 (for which the algorithm is already pretty fast).

First statistics on threshold tuning in hybrid algorithms.

Jensen-Fortin-Buzdalov hybridized with ENS-SS

Dataset: Uniform Hypercube

2 threads (best speed-up 1.889)

N\D 4 5 6 7 8 9 10
100000 1.409 1.634 1.696 1.707 1.736 1.703 1.719
316227 1.502 1.725 1.764 1.798 1.837 1.817 1.844
1000000 1.568 1.739 1.839 1.887 1.830 1.866 1.889

3 threads (best speed-up 3.020)

N\D 4 5 6 7 8 9 10
100000 1.504 1.953 2.125 2.285 2.258 1.905 2.265
316227 1.654 2.193 2.368 2.552 2.665 1.952 2.595
1000000 1.787 2.398 2.726 2.924 2.943 3.020 2.958

4 threads (best speed-up 3.351)

N\D 4 5 6 7 8 9 10
100000 1.702 2.228 2.477 2.566 2.607 2.563 2.572
316227 1.916 2.507 2.802 2.954 2.995 3.024 3.053
1000000 2.057 2.704 3.049 3.250 3.261 3.268 3.351

5 threads (best speed-up 3.501)

N\D 4 5 6 7 8 9 10
100000 1.701 2.242 2.522 2.550 2.662 2.631 2.642
316227 1.921 2.583 2.922 3.057 3.094 3.145 3.156
1000000 2.089 2.780 3.209 3.442 3.384 3.445 3.501

6 threads (best speed-up 3.994)

N\D 4 5 6 7 8 9 10
100000 1.745 2.299 2.663 2.779 2.844 2.834 2.846
316227 1.978 2.756 3.146 3.314 3.468 3.493 3.524
1000000 2.160 3.010 3.531 3.818 3.927 3.904 3.994

7 threads (best speed-up 4.283)

N\D 4 5 6 7 8 9 10
100000 1.760 2.368 2.733 2.815 2.892 2.848 2.881
316227 2.036 2.821 3.285 3.507 3.612 3.615 3.641
1000000 2.249 3.201 3.715 4.096 4.122 4.165 4.283

8 threads (best speed-up 4.446)

N\D 4 5 6 7 8 9 10
100000 1.798 2.451 2.797 2.889 2.995 2.927 2.971
316227 2.094 2.933 3.398 3.623 3.778 3.780 3.816
1000000 2.318 3.263 3.894 4.252 4.311 4.369 4.446

Dataset: Uniform Hyperplane

2 threads (best speed-up 1.871)

N\D 4 5 6 7 8 9 10
100000 1.281 1.508 1.617 1.602 1.678 1.677 1.721
316227 1.393 1.628 1.712 1.756 1.765 1.818 1.777
1000000 1.452 1.659 1.798 1.779 1.847 1.869 1.871

3 threads (best speed-up 3.302)

N\D 4 5 6 7 8 9 10
100000 1.350 1.793 2.109 2.035 2.231 2.254 2.405
316227 1.492 2.020 2.471 2.644 2.753 2.708 2.800
1000000 1.602 2.329 2.766 2.954 3.055 3.150 3.302

4 threads (best speed-up 3.594)

N\D 4 5 6 7 8 9 10
100000 1.432 1.856 2.177 2.149 2.230 2.319 2.479
316227 1.616 2.213 2.565 2.704 2.868 3.022 3.097
1000000 1.785 2.455 3.036 3.338 3.594 3.175 3.527

5 threads (best speed-up 3.737)

N\D 4 5 6 7 8 9 10
100000 1.454 1.961 2.196 2.310 2.374 2.489 2.624
316227 1.674 2.231 2.664 2.802 2.932 2.979 2.991
1000000 1.848 2.668 3.275 3.006 3.604 3.347 3.737

6 threads (best speed-up 3.878)

N\D 4 5 6 7 8 9 10
100000 1.453 2.007 2.285 2.386 2.572 2.673 2.732
316227 1.692 2.403 2.863 3.044 3.184 3.292 3.294
1000000 1.888 2.710 3.210 3.420 3.677 3.722 3.878

7 threads (best speed-up 4.098)

N\D 4 5 6 7 8 9 10
100000 1.490 2.011 2.408 2.473 2.639 2.709 2.731
316227 1.705 2.438 2.919 3.098 3.292 3.487 3.444
1000000 1.889 2.769 3.393 3.587 3.841 3.970 4.098

8 threads (best speed-up 4.272)

N\D 4 5 6 7 8 9 10
100000 1.498 2.097 2.419 2.531 2.704 2.720 2.869
316227 1.737 2.506 3.014 3.216 3.357 3.536 3.564
1000000 1.929 2.861 3.397 3.650 4.025 4.142 4.272

Jensen-Fortin-Buzdalov hybridized with ENS-NDT

Dataset: Uniform Hypercube

2 threads (best speed-up 1.713)

N\D 4 5 6 7 8 9 10
100000 1.353 1.400 1.352 1.312 1.330 1.363 1.372
316227 1.378 1.497 1.502 1.471 1.497 1.485 1.511
1000000 1.570 1.622 1.663 1.683 1.679 1.693 1.713

3 threads (best speed-up 2.114)

N\D 4 5 6 7 8 9 10
100000 1.440 1.536 1.410 1.359 1.342 1.383 1.386
316227 1.527 1.725 1.577 1.580 1.613 1.550 1.554
1000000 1.753 2.102 2.114 2.091 2.008 2.108 2.060

4 threads (best speed-up 2.440)

N\D 4 5 6 7 8 9 10
100000 1.565 1.670 1.538 1.479 1.468 1.526 1.531
316227 1.707 1.876 1.837 1.816 1.764 1.798 1.784
1000000 2.063 2.335 2.382 2.401 2.372 2.440 2.352

5 threads (best speed-up 2.479)

N\D 4 5 6 7 8 9 10
100000 1.596 1.660 1.553 1.491 1.470 1.514 1.538
316227 1.709 1.904 1.883 1.821 1.795 1.815 1.856
1000000 2.098 2.375 2.441 2.463 2.441 2.445 2.479

6 threads (best speed-up 2.671)

N\D 4 5 6 7 8 9 10
100000 1.630 1.693 1.533 1.492 1.508 1.517 1.532
316227 1.772 1.992 1.908 1.873 1.846 1.839 1.923
1000000 2.235 2.545 2.561 2.610 2.586 2.596 2.671

7 threads (best speed-up 2.677)

N\D 4 5 6 7 8 9 10
100000 1.675 1.708 1.553 1.511 1.505 1.512 1.521
316227 1.808 2.030 1.914 1.880 1.837 1.839 1.893
1000000 2.290 2.621 2.632 2.633 2.604 2.637 2.677

8 threads (best speed-up 2.721)

N\D 4 5 6 7 8 9 10
100000 1.687 1.731 1.557 1.492 1.484 1.505 1.491
316227 1.845 2.040 1.942 1.860 1.842 1.837 1.890
1000000 2.346 2.669 2.675 2.667 2.645 2.675 2.721

Dataset: Uniform Hyperplane

2 threads (best speed-up 1.623)

N\D 4 5 6 7 8 9 10
100000 1.260 1.312 1.288 1.292 1.312 1.296 1.280
316227 1.328 1.407 1.378 1.384 1.390 1.421 1.431
1000000 1.419 1.565 1.563 1.560 1.584 1.598 1.623

3 threads (best speed-up 2.005)

N\D 4 5 6 7 8 9 10
100000 1.282 1.428 1.336 1.306 1.319 1.315 1.327
316227 1.472 1.636 1.529 1.480 1.429 1.451 1.440
1000000 1.600 1.966 1.990 1.907 1.883 1.645 2.005

4 threads (best speed-up 2.165)

N\D 4 5 6 7 8 9 10
100000 1.469 1.488 1.426 1.397 1.375 1.419 1.457
316227 1.582 1.717 1.615 1.605 1.626 1.689 1.673
1000000 1.782 2.099 2.128 2.076 2.128 2.146 2.165

5 threads (best speed-up 2.266)

N\D 4 5 6 7 8 9 10
100000 1.503 1.496 1.405 1.401 1.426 1.432 1.455
316227 1.616 1.724 1.624 1.617 1.629 1.680 1.681
1000000 1.834 2.127 2.139 2.134 2.188 2.207 2.266

6 threads (best speed-up 2.389)

N\D 4 5 6 7 8 9 10
100000 1.509 1.499 1.406 1.402 1.426 1.421 1.443
316227 1.620 1.762 1.674 1.603 1.652 1.694 1.704
1000000 1.865 2.222 2.233 2.241 2.259 2.302 2.389

7 threads (best speed-up 2.390)

N\D 4 5 6 7 8 9 10
100000 1.523 1.464 1.405 1.411 1.422 1.432 1.468
316227 1.653 1.758 1.633 1.615 1.641 1.690 1.717
1000000 1.910 2.251 2.232 2.234 2.275 2.340 2.390

8 threads (best speed-up 2.408)

N\D 4 5 6 7 8 9 10
100000 1.537 1.484 1.407 1.415 1.414 1.403 1.460
316227 1.673 1.777 1.673 1.601 1.649 1.669 1.703
1000000 1.918 2.274 2.257 2.239 2.299 2.324 2.408
Loading

Submission to EMO-2019

20 Dec 20:12
@mbuzdalov mbuzdalov
v0.2
02cef87
Compare
Choose a tag to compare
Submission to EMO-2019 Pre-release
Pre-release

This is the release that accompanies the paper called

"Make Evolutionary Multiobjective Algorithms Scale Better with Advanced Data Structures: Van Emde Boas Tree for Non-Dominated Sorting"

by Maxim Buzdalov (@mbuzdalov) which was submitted to the EMO-2019 conference.

Loading

Submission for PPSN 2018

03 Apr 12:44
@mbuzdalov mbuzdalov
v0.1
95b2e27
This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Verified
Learn about vigilant mode.
Compare
Choose a tag to compare
Submission for PPSN 2018 Pre-release
Pre-release

This is the release that accompanies the paper called

"Towards Large-Scale Multiobjective Optimization: Extremely Fast Hybrid Non-Dominated Sorting"

by Margarita Markina (@markina) and Maxim Buzdalov (@mbuzdalov), which is submitted to the Parallel Problem Solving from Nature conference (PPSN).

Below come the plots of the running times for the following algorithms:

  • the divide-and-conquer algorithm: JensenFortinBuzdalov.getRedBlackTreeSweepImplementation(1);
  • the non-dominated tree algorithm (ENS-NDT) with split threshold size 8: ENS.getENS_NDT(8);
  • the single-tree non-dominated tree algorithm (ENS-NDT-ONE) with split threshold size 8: ENS.getENS_NDT_OneTree(8);
  • the hybrid algorithm (tree split threshold size 8, switch-to-tree threshold 100 for dimension 3, 20000 for larger dimensions): JensenFortinBuzdalov.getRedBlackTreeSweepHybridNDTImplementation(8).

uniform hypercube d3
uniform hypercube d5
uniform hypercube d7
uniform hypercube d10
uniform hypercube d15
uniform hyperplane d3
uniform hyperplane d5
uniform hyperplane d7
uniform hyperplane d10
uniform hyperplane d15

Loading