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

Comparison of the grid/cloud computing frameworks (Hadoop, GridGain, Hazelcast, DAC) - part I

---

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:

•  http://www.mathpages.com/home/kmath030.htm

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):

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.

2. Decrease in number of tasks below the amount of available processors significantly increases the time of computation.

3. 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.

4. We can seriously decrease the average time needed to solve our problems when we compute them using Dynamic Agent Computations Framework.