# Results: Algorithm Comparison¶

Faster Multi-Object Segmentation using Parallel Quadratic Pseudo-Boolean Optimization, ICCV 2021 Paper

Authors: Patrick M. Jensen (patmjen@dtu.dk) and Niels Jeppesen (niejep@dtu.dk)

This notebook is used to analyze the benchmark results for the comparison between P-QPBO and a few non-QPBO solves (see paper for more details).

Note: The code for the non-QPBO methods used to generate the CSV files summarised here is not included in this paper's subplementary material. However, the code is available at https://github.com/patmjen/maxflow_algorithms.

In [1]:

    import numpy as np
    import pandas as pd
    from glob import glob

    import matplotlib.pyplot as plt

## Nuclei segmentation results (BBB)¶

Comparing results for the nuclei segmentation task.

### Read data¶

First, we read the results from the CSV files.

In [2]:

    qpbo_data = pd.read_csv('../benchmark/nuclei_benchmarks/qpbo/parallel_qpbo_nuclei_benchmark_results_20201011-172857.csv')

In [3]:

    most_data = pd.concat([pd.read_csv(f) for f in glob('../benchmark/nuclei_benchmarks/all/*.csv')])

In [4]:

    most_data['Name'] = most_data['file_name'].apply(lambda n: n.split('/')[-1][:-3])
    most_data['SolveTime'] = most_data['solve_time']
    most_data['ShortName'] = most_data['algorithm']
    most_data['NucleiCount'] = most_data['num_blocks']
    most_data['CpuCount'] = most_data['num_threads']

In [5]:

    peibfs_data = pd.concat([pd.read_csv(f) for f in glob('../benchmark/nuclei_benchmarks/peibfs/*.csv')])

In [6]:

    peibfs_data['Name'] = peibfs_data['file_name'].apply(lambda n: n.split('/')[-1][:-3])
    peibfs_data['SolveTime'] = peibfs_data['solve_time']
    peibfs_data['ShortName'] = peibfs_data['algorithm']
    peibfs_data['NucleiCount'] = peibfs_data['num_blocks']
    peibfs_data['CpuCount'] = peibfs_data['num_threads']

In [7]:

    # Make a nice dataframe which only has the columns we need
    keep_columns = ['Name', 'ShortName', 'NucleiCount', 'SolveTime', 'CpuCount']
    all_data = pd.concat([most_data[keep_columns], qpbo_data[keep_columns], peibfs_data[keep_columns]])

In [8]:

    # Only keep entries for datasets where all algorithms have run at least once
    keep_names = list(set(most_data['Name']).intersection(set(qpbo_data['Name'])).intersection(set(peibfs_data['Name'])))
    all_data = all_data[all_data['Name'].isin(keep_names)]
    print(f'Number of datasets: {len(keep_names)}/670')

    Number of datasets: 669/670

In [9]:

    # Make sure all algorithms are present
    data = all_data.groupby(['Name', 'ShortName', 'CpuCount']).min().reset_index()
    data['ShortName'].unique()

Out[9]:

    array(['Para (1)', 'Para (16)', 'Para (2)', 'Para (24)', 'Para (32)',
           'Para (4)', 'Para (6)', 'Para (8)', 'QPBO', 'Qpbo', 'eibfs',
           'eibfs_old', 'peibfs', 'pmbk'], dtype=object)

### Investigate speed-up¶

In [10]:

    # Compute speed-up w.r.t K-QPBO
    data2 = data.set_index('Name')
    data2['SpeedUp'] = 1 / data2['SolveTime'].divide(data2[data2['ShortName'] == 'QPBO']['SolveTime'])

In [11]:

    print('Mean speed-up')
    print(data2.groupby(['ShortName', 'CpuCount']).mean()['SpeedUp'])

    Mean speed-up
    ShortName  CpuCount
    Para (1)    1          1.386163
    Para (16)   16         2.123567
    Para (2)    2          2.174207
    Para (24)   24         1.869330
    Para (32)   32         1.811058
    Para (4)    4          2.957527
    Para (6)    6          2.882809
    Para (8)    8          2.685858
    QPBO       -1          1.000000
    Qpbo       -1          1.718092
    eibfs       1          0.331549
    eibfs_old   1          0.292372
    peibfs      1          0.445261
                2          0.541480
                4          0.622951
                8          0.671057
                16         0.682280
    pmbk        1          0.625946
                2          0.783782
                4          0.738600
                8          0.663402
                16         0.645193
    Name: SpeedUp, dtype: float64

In [12]:

    print('Speed-up std.')
    print(data2.groupby(['ShortName', 'CpuCount']).std()['SpeedUp'])

    Speed-up std.
    ShortName  CpuCount
    Para (1)    1          0.256511
    Para (16)   16         0.644479
    Para (2)    2          0.501759
    Para (24)   24         0.509253
    Para (32)   32         0.465281
    Para (4)    4          0.887464
    Para (6)    6          0.943767
    Para (8)    8          0.903815
    QPBO       -1          0.000000
    Qpbo       -1          0.275681
    eibfs       1          0.075951
    eibfs_old   1          0.069807
    peibfs      1          0.110960
                2          0.119529
                4          0.120537
                8          0.128651
                16         0.135971
    pmbk        1          0.095952
                2          0.125563
                4          0.146391
                8          0.119306
                16         0.117935
    Name: SpeedUp, dtype: float64

## Nerve segmentation results (N1)¶

Comparing results for the nerve segmentation task.

### Read data for QPBO method¶

We read the results from the CSV files.

In [13]:

    benchmark_paths = glob('../benchmark/nerve_benchmarks/parallel_qpbo_benchmark_results_*.csv')
    benchmark_paths

Out[13]:

    ['../benchmark/nerve_benchmarks\\parallel_qpbo_benchmark_results_20210617-130430.csv',
     '../benchmark/nerve_benchmarks\\parallel_qpbo_benchmark_results_20210617-175617.csv']

In [14]:

    df_qpbo = pd.concat([pd.read_csv(p) for p in benchmark_paths])
    df_qpbo = df_qpbo[df_qpbo['CpuCount'] <= 32]
    df_qpbo_group = df_qpbo.groupby(['NodeCount', 'EdgeCount', 'Class', 'SystemCpu', 'CpuCount'])
    df_qpbo_group[['SolveTime']].describe()

Out[14]:

|  |  |  |  | SolveTime
--- | --- | --- | --- | --- | ---
|  |  |  |  | count | mean | std | min | 25% | 50% | 75% | max
NodeCount | EdgeCount | Class | SystemCpu | CpuCount |  |  |  |  |  |  |  |
363748800 | 2124073454 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | 1 | 10.0 | 579.307223 | 11.875941 | 558.328071 | 578.605085 | 582.126613 | 585.055149 | 594.456977
2 | 10.0 | 319.854369 | 1.576121 | 317.279246 | 318.922619 | 319.809541 | 320.916663 | 322.176483
4 | 10.0 | 195.173083 | 1.620437 | 192.559520 | 194.516620 | 195.562399 | 195.923060 | 197.797684
8 | 10.0 | 131.076683 | 2.272190 | 128.020746 | 129.337352 | 131.077217 | 132.822038 | 134.440500
16 | 10.0 | 97.358785 | 2.053922 | 94.463284 | 95.732710 | 97.290871 | 99.037019 | 100.375021
24 | 10.0 | 90.315316 | 3.335071 | 83.846947 | 87.996215 | 90.835559 | 92.905286 | 94.450838
32 | 10.0 | 86.877261 | 3.241845 | 79.910048 | 85.663351 | 87.359990 | 88.837200 | 90.543388
QPBOInt | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | -1 | 10.0 | 841.373733 | 4.298516 | 836.261239 | 836.729420 | 843.534726 | 843.862978 | 848.021129
QpboCapInt32ArcIdxUInt32NodeIdxUInt32 | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | -1 | 10.0 | 627.905059 | 0.083595 | 627.784739 | 627.860083 | 627.894342 | 627.978344 | 628.024728
818434800 | 4864255488 | ParallelQpboCapInt32ArcIdxUInt64NodeIdxUInt32 | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | 1 | 3.0 | 2531.628094 | 96.514441 | 2429.012243 | 2487.149097 | 2545.285952 | 2582.936020 | 2620.586087
2 | 3.0 | 1374.460305 | 3.726936 | 1370.174875 | 1373.218386 | 1376.261898 | 1376.603021 | 1376.944144
4 | 3.0 | 796.362165 | 1.229802 | 794.954621 | 795.928841 | 796.903061 | 797.065936 | 797.228811
8 | 3.0 | 472.311812 | 2.091032 | 471.016149 | 471.105661 | 471.195172 | 472.959643 | 474.724114
16 | 3.0 | 325.156917 | 2.024735 | 322.850512 | 324.414543 | 325.978575 | 326.310120 | 326.641664
24 | 3.0 | 284.964727 | 9.873397 | 276.624371 | 279.513898 | 282.403425 | 289.134905 | 295.866385
32 | 3.0 | 268.076653 | 3.722665 | 263.876128 | 266.631259 | 269.386390 | 270.176916 | 270.967441
QPBOInt | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | -1 | 3.0 | 5127.883808 | 187.043128 | 4986.645045 | 5021.821307 | 5056.997570 | 5198.503190 | 5340.008811
QpboCapInt32ArcIdxUInt64NodeIdxUInt32 | Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz | -1 | 3.0 | 3772.888895 | 85.631975 | 3703.791146 | 3724.987831 | 3746.184516 | 3807.437769 | 3868.691022

### Calculate N1 speed-up¶

In [15]:

    qpbo_mins = df_qpbo_group['SolveTime'].min().reset_index()
    qpbo_mins_n1 = qpbo_mins[qpbo_mins['NodeCount'] == 363748800].copy()
    qpbo_mins_n1['SpeedUp'] = qpbo_mins_n1[qpbo_mins_n1['Class'] == 'QPBOInt']['SolveTime'].iloc[0] / qpbo_mins_n1['SolveTime']
    qpbo_mins_n1[['Class', 'CpuCount', 'SolveTime', 'SpeedUp']]

Out[15]:

| Class | CpuCount | SolveTime | SpeedUp
--- | --- | --- | --- | ---
0 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 1 | 558.328071 | 1.497795
1 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 2 | 317.279246 | 2.635726
2 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 4 | 192.559520 | 4.342871
3 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 8 | 128.020746 | 6.532232
4 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 16 | 94.463284 | 8.852765
5 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 24 | 83.846947 | 9.973664
6 | ParallelQpboCapInt32ArcIdxUInt32NodeIdxUInt32 | 32 | 79.910048 | 10.465032
7 | QPBOInt | -1 | 836.261239 | 1.000000
8 | QpboCapInt32ArcIdxUInt32NodeIdxUInt32 | -1 | 627.784739 | 1.332083

### Read data for non-QPBO method¶

We read the results from the CSV files.

In [16]:

    benchmark_paths = glob('../benchmark/nerve_benchmarks/bench*.csv')
    benchmark_paths

Out[16]:

    ['../benchmark/nerve_benchmarks\\bench_eibfs_n216_10120507.csv',
     '../benchmark/nerve_benchmarks\\bench_eibfs_n216_10120508.csv',
     '../benchmark/nerve_benchmarks\\bench_peibfs_n21610118299.csv',
     '../benchmark/nerve_benchmarks\\bench_peibfs_n21610118300.csv',
     '../benchmark/nerve_benchmarks\\bench_pmbk_n21610118296.csv',
     '../benchmark/nerve_benchmarks\\bench_pmbk_n21610118297.csv']

In [17]:

    df_maxflow = pd.concat([pd.read_csv(p) for p in benchmark_paths])

    df_maxflow = df_maxflow[df_maxflow['num_threads'] <= 32]
    df_maxflow_group = df_maxflow.groupby(['num_nodes', 'num_term_arcs', 'bench_name', 'num_threads'])
    df_maxflow_group[['solve_time']].describe()

Out[17]:

|  |  |  | solve_time
--- | --- | --- | --- | ---
|  |  |  | count | mean | std | min | 25% | 50% | 75% | max
num_nodes | num_term_arcs | bench_name | num_threads |  |  |  |  |  |  |  |
363748800 | 363748800 | ICCV2021 EIBFS N1 | 1 | 10.0 | 787.5001 | 12.754552 | 772.073 | 773.01500 | 795.7650 | 796.62150 | 800.593
ICCV2021 PEIBFS N1 | 8 | 10.0 | 1436.2390 | 60.638976 | 1388.290 | 1398.23250 | 1406.5950 | 1457.32750 | 1588.280
16 | 10.0 | 1381.0960 | 39.089918 | 1319.900 | 1353.76250 | 1375.4750 | 1408.12000 | 1435.890
24 | 10.0 | 1347.8810 | 24.638453 | 1317.690 | 1331.34750 | 1344.5050 | 1367.21000 | 1390.700
32 | 10.0 | 1375.3650 | 58.197024 | 1330.260 | 1335.54500 | 1350.0300 | 1392.71750 | 1490.570
ICCV2021 PMBK N1 | 8 | 10.0 | 275.4531 | 2.954681 | 269.853 | 274.08225 | 276.1115 | 277.06625 | 279.262
16 | 10.0 | 181.3881 | 5.946143 | 175.437 | 175.76725 | 180.4350 | 185.68975 | 190.804
24 | 10.0 | 157.6547 | 4.891746 | 149.442 | 155.39175 | 156.9285 | 159.83275 | 168.290
32 | 10.0 | 143.1197 | 4.195206 | 137.801 | 139.16400 | 143.9395 | 145.23400 | 149.758

### Calculate N1 speed-up¶

In [18]:

    maxflow_mins = df_maxflow_group['solve_time'].min().reset_index()
    maxflow_mins_n1 = maxflow_mins[maxflow_mins['num_nodes'] == 363748800].copy()
    maxflow_mins_n1['SpeedUp'] = qpbo_mins_n1[qpbo_mins_n1['Class'] == 'QPBOInt']['SolveTime'].iloc[0] / maxflow_mins_n1['solve_time']
    maxflow_mins_n1[['bench_name', 'num_threads', 'solve_time', 'SpeedUp']]

Out[18]:

| bench_name | num_threads | solve_time | SpeedUp
--- | --- | --- | --- | ---
0 | ICCV2021 EIBFS N1 | 1 | 772.073 | 1.083138
1 | ICCV2021 PEIBFS N1 | 8 | 1388.290 | 0.602368
2 | ICCV2021 PEIBFS N1 | 16 | 1319.900 | 0.633579
3 | ICCV2021 PEIBFS N1 | 24 | 1317.690 | 0.634642
4 | ICCV2021 PEIBFS N1 | 32 | 1330.260 | 0.628645
5 | ICCV2021 PMBK N1 | 8 | 269.853 | 3.098951
6 | ICCV2021 PMBK N1 | 16 | 175.437 | 4.766732
7 | ICCV2021 PMBK N1 | 24 | 149.442 | 5.595892
8 | ICCV2021 PMBK N1 | 32 | 137.801 | 6.068615

In [19]:

    maxflow_mins_n1.groupby(['bench_name'])['SpeedUp'].max()

Out[19]:

    bench_name
    ICCV2021 EIBFS N1     1.083138
    ICCV2021 PEIBFS N1    0.634642
    ICCV2021 PMBK N1      6.068615
    Name: SpeedUp, dtype: float64

In [20]:

    print('EIBFS-QPBO estimate:', maxflow_mins_n1.groupby(['bench_name'])['SpeedUp'].max()['ICCV2021 EIBFS N1'] * 2)

    EIBFS-QPBO estimate: 2.166275050610452

In [ ]: