Navigation


This is a DAC 0.7.1 efficiency tests page. If you are looking for comparison with other frameworks, please look at:


Efficiency Tests

CMBF - Counting Monotone Boolean Functions

Counting monotone boolean functions is also known as Dedekind's problem. You can find more information about that on:

Average time of the efficiency tests based on CMBF problem

The above graph is a gentle presentation of our efficiency test results:

  • X-axis: number of tasks the problem was divided to
  • Y-axis: average time of the algorithm (in milliseconds)



Average time of the algorithm (for better view results in seconds):

Number of tasks 30 341 2705 33700
Agent CMBF 468,5 305,83 299,51 304,97
Agent CMBFH 428,6 307,41 299,64 309,11
Single-threaded v1 8346,31 8299,81 8336,09 8403,93
Single-threaded v2 11762,48 11890,17 11888,58 11946,25


You can also look at the diagram presenting the cumulative cost of the algorithms (in milliseconds):

Cumulative cost of the efficiency tests based on CMBF problem

You will find a more detailed results, description of the methodology and conclusions in the following paragraphs.

Methodology

Efficiency tests were based on agents counting monotone boolean functions. The problem was solved in two ways:

  • by means of flat CMBF agent: at the beginning, all CMBF agents that were required for computation were created. Afterwards, they were sent to the broker, and finally the results were gathered.
  • by means of hierarchical CMBFH agent: at the beginning there were created main agents for all types of images. Next, they were sent to the broker, where, if needed, they created new agents computing smaller parts of images. In the end, partial results were sent up in the hierarchy and gathered in one place.

Counting monotone boolean functions was prepared in four versions:

  • divided into 33700 tasks
  • divided into 2705 tasks
  • divided into 341 tasks
  • divided into 30 tasks

Testing environment consisted with 5 (intel1.ipipan.gda.pl-intel5.ipipan.gda.pl) machines, each one with 8 cpu on board, which gave us 40 processing units.

Broker was available on machine intel1.ipipan.gda.pl.
Launcher was started on machine dacframe.org.
40 workers were launched on intels (8 on each intel).

Results

All tests were repeated multiple times in order to avoid measuring error. The results are printed in milliseconds.

Agent CMBF

Number of tasks 33700 2705 341 30
1st time 305237 299674 304712 434510
2nd time 304368 299328 305851 487521
3rd time 304386 299489 306385 463961
4th time 304814 299561 304157 453378
5th time 304576 299779 305779 506400
6th time 304799 299221 305139 511996
7th time 304393 299341 308964 517020
8th time 304765 299571 306199 469004
9th time 304809 299242 303721 434393
10th time 304738 299273 305497 429175
11th time 305048 299512 306408 459840
12th time 304691 300109 304491 431407
13th time 304613 299634 304884 484247
14th time 304819 299456 306310 468746
15th time 304821 299524 305798 446402
16th time 305059 299801 303912 451471
17th time 304851 299670 304395 459411
18th time 304669 299382 306438 452807
19th time 305214 299426 303155 455941
20th time 304960 299338 306498 480229
21st time 304913 299251 304272 472116
22nd time 305024 299716 306483 496207
23rd time 305014 299408 308373 440232
24th time 305267 299888 307828 494297
25th time 306367 299406 307296 454757
26th time 305361 299413 306213 516911
27th time 305342 299151 307671 487708
28th time 305317 299440 306499 460730
29th time 305396 299907 306652 411207
30th time 305527 299320 305061 522948
Average 304971,93 299507,7 305834,7 468499,07
Std Deviation 407,61 229,71 1402,32 29192,88

Agent CMBFH

Number of tasks 33700 2705 341 30
1st time 310077 300012 306911 410462
2nd time 309316 299480 310779 436495
3rd time 309010 299398 304947 405881
4th time 308928 299551 305801 491248
5th time 309143 299874 305236 419787
6th time 308376 299536 306012 427612
7th time 309770 299360 305558 454597
8th time 309834 300118 306903 375817
9th time 310362 299667 307569 514054
10th time 308325 299175 308396 379723
11th time 308604 299791 308101 417851
12th time 310189 299510 305810 458546
13th time 310359 299253 311193 434958
14th time 308881 299348 307829 405941
15th time 309078 299819 305008 425843
16th time 310534 300038 306414 430806
17th time 309117 299835 308552 417556
18th time 310309 299607 309061 431454
19th time 309478 299514 310212 435672
20th time 308091 299775 313677 385952
21st time 308158 299675 308299 422834
22nd time 308669 299620 308625 414679
23rd time 308247 300248 305176 423759
24th time 308330 299518 307027 414037
25th time 308794 299553 306188 493850
26th time 308681 299883 307424 434401
27th time 308750 299220 307699 435857
28th time 309071 299771 308399 412983
29th time 308155 299626 304249 431132
30th time 308798 299449 305342 414126
Average 309114,47 299640,8 307413,23 428597,1
Std Deviation 748,67 265,31 2127,72 30460,81

Single-threaded test v1

This test was performed using only single cpu from each machine at the same moment.

Number of tasks 33700 2705 341 30
1st time 8412777 8314064 8304007 8322661
2nd time 8406311 8332501 8291292 8341936
3th time 8395790 8327442 8296593 8373195
4th time 8396707 8343479 8252998 8349860
5th time 8383080 8335228 8277126 8334996
6th time 8386879 8331872 8293092 8331021
7th time 8403041 8318735 8276834 8329912
8th time 8402856 8344785 8329391 8343244
9th time 8374451 8344660 8296532 8359016
10th time 8406488 8317917 8325981 8348666
11th time 8424893 8320596 8321721 8375178
12th time 8429559 8354345 8278265 8334225
13th time 8421828 8332579 8306151 8348654
14th time 8406475 8336883 8302350 8350596
15th time 8412525 8353552 8325779 8362314
16th time 8397772 8347544 8281477 8349515
17th time 8397804 8348163 8305178 8346689
18th time 8411458 8345268 8331787 8331888
Average 8403927,44 8336089,61 8299808,56 8346309,22
Std Deviation 14213,56 12553 21697,04 14549,45

Single-threaded test v2

This test was performed using all 8 cpus from a single machine at the same moment.

Number of tasks 33700 2705 341 30
1 time 12085990 11859945 12170222 12015614
2 time 11764034 12235654 11555700 11861657
3 time 11888020 11900341 12214623 11397705
4 time 11831322 11998974 11789168 12143043
5 time 12382547 12161057 11980699 11867652
6 time 12194707 11971874 12243963 11051124
7 time 12042291 12203236 11654589 11998473
8 time 11717845 11714344 11965901 11989323
9 time 11997205 12106699 11885785 11653072
10 time 11827032 12065433 11963266 11968328
11 time 12070266 11720166 11579915 12148227
12 time 11845856 11822374 11805265 11360562
13 time 11735406 11731340 12061689 11839892
14 time 11903833 11717115 11966961 11828315
15 time 11821827 11701421 11662442 11659083
16 time 11902033 11965817 11862955 11745554
17 time 11844262 11673220 11947745 11531715
18 time 12134479 11841248 11606046 12002769
19 time 12189080 11693587 11555328 11594308
20 time 11878003 11861273 11776622 11783677
21 time 11710034 11666430 11966849 11886473
22 time 11901720 11527210 12196020 11606343
23 time 12051004 12091069 12139321 12128004
24 time 11991278 12096205 11813074 11238539
Average 11946253,08 11888584,67 11890172,83 11762477,17
Std Deviation 170549,53 198067,71 216052,75 291146,53

Cumulative cost

We can compare the above results using cumulative cost metric, i.e. number of used processors multiplied by the average processing time. This is shown in the following table:

Number of tasks 33700 2705 341 30
Agent CMBF 12198877,33 11980308 12233388 14054972
Agent CMBFH 12364578,67 11985632 12296529,33 12857913
Single-threaded v1 8403927,44 8336089,61 8299808,56 8346309,22
Single-threaded v2 11946253,08 11888584,67 11890172,83 11762477,17

Conclusions

  1. Significant growth of number of tasks to compute (from 341 to 33700) doesn't increase the time of computation -> Margin for communication is small.
  1. Decrease in number of tasks below the amount of available processors significantly increases the time of computation.
  1. The cumulative cost of the properly distributed computation is the same as a single threaded version. We can see this by comparing results for Agent CMBF and Single-threaded v2 tests with 2705 tasks.
  1. We can seriously decrease the average time needed to solve our problems when we compute them using Dynamic Agent Computations Framework.

Attachments