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

  1. CMBF - Counting Monotone Boolean Functions
  2. Methodology
  3. Results
    1. Agent CMBF
    2. Agent CMBFH
    3. Single-threaded test v1
    4. Single-threaded test v2
    5. Cumulative cost
  4. Conclusions

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 tasks30341270533700
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 tasks33700270534130
1st time305237299674304712434510
2nd time304368299328305851487521
3rd time304386299489306385463961
4th time304814299561304157453378
5th time304576299779305779506400
6th time304799299221305139511996
7th time304393299341308964517020
8th time304765299571306199469004
9th time304809299242303721434393
10th time304738299273305497429175
11th time305048299512306408459840
12th time304691300109304491431407
13th time304613299634304884484247
14th time304819299456306310468746
15th time304821299524305798446402
16th time305059299801303912451471
17th time304851299670304395459411
18th time304669299382306438452807
19th time305214299426303155455941
20th time304960299338306498480229
21st time304913299251304272472116
22nd time305024299716306483496207
23rd time305014299408308373440232
24th time305267299888307828494297
25th time306367299406307296454757
26th time305361299413306213516911
27th time305342299151307671487708
28th time305317299440306499460730
29th time305396299907306652411207
30th time305527299320305061522948
Average304971,93299507,7305834,7468499,07
Std Deviation407,61229,711402,3229192,88

Agent CMBFH

Number of tasks33700270534130
1st time310077300012306911410462
2nd time309316299480310779436495
3rd time309010299398304947405881
4th time308928299551305801491248
5th time309143299874305236419787
6th time308376299536306012427612
7th time309770299360305558454597
8th time309834300118306903375817
9th time310362299667307569514054
10th time308325299175308396379723
11th time308604299791308101417851
12th time310189299510305810458546
13th time310359299253311193434958
14th time308881299348307829405941
15th time309078299819305008425843
16th time310534300038306414430806
17th time309117299835308552417556
18th time310309299607309061431454
19th time309478299514310212435672
20th time308091299775313677385952
21st time308158299675308299422834
22nd time308669299620308625414679
23rd time308247300248305176423759
24th time308330299518307027414037
25th time308794299553306188493850
26th time308681299883307424434401
27th time308750299220307699435857
28th time309071299771308399412983
29th time308155299626304249431132
30th time308798299449305342414126
Average309114,47299640,8307413,23428597,1
Std Deviation748,67265,312127,7230460,81

Single-threaded test v1

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

Number of tasks33700270534130
1st time8412777831406483040078322661
2nd time8406311833250182912928341936
3th time8395790832744282965938373195
4th time8396707834347982529988349860
5th time8383080833522882771268334996
6th time8386879833187282930928331021
7th time8403041831873582768348329912
8th time8402856834478583293918343244
9th time8374451834466082965328359016
10th time8406488831791783259818348666
11th time8424893832059683217218375178
12th time8429559835434582782658334225
13th time8421828833257983061518348654
14th time8406475833688383023508350596
15th time8412525835355283257798362314
16th time8397772834754482814778349515
17th time8397804834816383051788346689
18th time8411458834526883317878331888
Average8403927,448336089,618299808,568346309,22
Std Deviation14213,561255321697,0414549,45

Single-threaded test v2

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

Number of tasks33700270534130
1 time12085990118599451217022212015614
2 time11764034122356541155570011861657
3 time11888020119003411221462311397705
4 time11831322119989741178916812143043
5 time12382547121610571198069911867652
6 time12194707119718741224396311051124
7 time12042291122032361165458911998473
8 time11717845117143441196590111989323
9 time11997205121066991188578511653072
10 time11827032120654331196326611968328
11 time12070266117201661157991512148227
12 time11845856118223741180526511360562
13 time11735406117313401206168911839892
14 time11903833117171151196696111828315
15 time11821827117014211166244211659083
16 time11902033119658171186295511745554
17 time11844262116732201194774511531715
18 time12134479118412481160604612002769
19 time12189080116935871155532811594308
20 time11878003118612731177662211783677
21 time11710034116664301196684911886473
22 time11901720115272101219602011606343
23 time12051004120910691213932112128004
24 time11991278120962051181307411238539
Average11946253,0811888584,6711890172,8311762477,17
Std Deviation170549,53198067,71216052,75291146,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 tasks33700270534130
Agent CMBF12198877,33119803081223338814054972
Agent CMBFH12364578,671198563212296529,3312857913
Single-threaded v18403927,448336089,618299808,568346309,22
Single-threaded v211946253,0811888584,6711890172,8311762477,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