kshireesh
asked on
does any body know what algorithum for the data given below?
You are to write a program to simulate a server which processes incoming requests. The simulation should show the optimum number of threads for this server and this data set. You may use one of the languages Java for the simulation.
Obtain the text data file appropriate to your section. You should save it and edit the file to remove the html tags. The file should look like a list of arrival times of requests and the time the server requires to process the request. Both of these times are in milliseconds.
Suppose the first few lines in the editted file are:
0 11
18 74
29 20
In a single threaded server: at 0 ms a request requiring 11 ms of processing arrives; the next request arrives at 18 ms and requires 74 ms to process; the third request arrives at 29 ms but cannot be started until the second request is finished. This results in a total time to process the three requests is 112 ms and average requests per second is 26.8 [(1/112)*1000].
In a two threaded server: at 0 ms a request requiring 11 ms of processing arrives; the next request arrives at 18 ms and requires 74 ms to process; the third request arrives at 29 ms and causes a second thread to start processing the request for 20 ms. The total processing time is 92 ms for the three requests and an average requests per second of 32.6 [(3/92)*1000].
Additional threads would not result in a better requests per second value. Therefore for this (admittedly small) input set the optimum number of threads is 2.
0 15
10 18
15 7
19 7
21 69
24 47
37 27
42 62
43 19
56 27
63 15
65 75
71 33
81 47
86 7
89 68
101 7
105 47
112 18
119 27
123 16
133 18
134 7
141 15
150 29
157 18
165 27
165 48
180 27
183 45
184 58
198 28
205 48
208 65
213 8
226 19
230 7
236 71
246 28
249 59
257 18
265 27
267 15
280 9
286 68
290 15
299 7
307 69
310 15
315 29
330 38
334 15
335 23
346 9
352 52
356 19
361 34
370 48
377 29
378 60
391 51
392 27
401 63
409 54
410 34
422 22
425 7
427 46
440 32
443 21
446 45
455 34
464 17
464 20
470 29
485 27
485 48
485 71
500 28
506 23
507 50
515 7
525 52
530 28
534 58
543 15
545 27
559 22
561 9
567 46
576 9
584 58
585 15
595 27
605 60
609 48
612 31
626 22
628 45
631 27
646 27
646 59
647 18
661 9
670 45
676 28
676 69
688 45
693 34
705 64
706 55
712 27
726 23
727 28
727 47
743 28
745 48
751 61
760 33
763 15
777 9
779 70
781 45
795 7
805 45
808 58
813 8
825 45
829 37
830 68
843 53
844 31
851 62
859 8
863 17
875 59
876 29
885 15
892 27
902 24
905 54
911 32
923 68
926 7
928 17
941 29
944 58
946 16
956 8
964 19
965 18
973 29
982 15
988 7
994 18
1004 31
1006 53
1015 18
1019 7
1024 49
1036 63
1038 7
1042 15
1053 9
1057 20
1065 46
1068 29
1078 18
1083 35
1083 49
1098 7
1100 19
1104 45
1116 28
1121 18
1126 55
1134 35
1142 18
1144 54
1149 7
1164 28
1165 15
1171 69
1179 8
1183 57
1194 27
1197 70
1201 18
1209 29
1218 21
1223 17
1227 7
1241 17
1245 30
1245 58
1260 45
1262 31
1267 62
1277 7
1283 55
1290 21
1292 7
1301 56
1309 29
1313 20
1319 18
1324 7
1334 67
1338 54
1339 32
1355 71
1357 31
1358 15
1372 30
1378 18
1380 48
1390 7
1398 18
1401 58
1407 7
1419 45
1422 61
1425 37
1439 55
1443 27
1443 63
1457 15
1458 7
1464 63
1473 7
1475 17
1485 61
1492 28
1494 53
1506 23
1507 29
1512 17
1525 31
1529 58
1531 15
1540 7
1550 70
1555 31
1555 45
1570 35
1573 15
1573 61
1589 27
1591 15
1602 69
1604 7
1612 15
1621 9
1623 21
1631 55
1636 7
1644 18
1649 15
1653 27
1667 56
1671 7
1672 24
1685 47
1686 27
1693 24
1701 29
1703 15
1718 31
1720 59
1724 55
1733 9
1744 15
1745 58
1749 27
1762 53
1766 29
1766 66
1781 34
1784 54
1787 63
1796 27
1806 19
1808 23
1811 7
1826 7
1829 16
1829 19
1843 30
1847 46
1850 18
1861 29
1865 56
1875 58
1879 31
1883 17
1894 8
1896 18
1901 19
1909 27
1920 50
1923 22
1928 8
1942 45
1943 27
1944 20
1958 7
1966 54
1971 20
1973 27
1988 7
1990 15
1996 65
2006 27
2012 18
2024 28
2025 22
2030 47
2043 27
2046 18
2048 47
2060 9
2066 16
2067 71
2075 34
2084 45
2088 24
2090 27
2106 15
2106 9
2113 60
2123 29
2126 19
2134 22
2142 7
2144 45
2155 60
2160 7
2162 17
2175 27
2181 15
2184 58
2190 33
2199 60
2206 29
2208 58
2217 45
2221 7
2235 53
2235 72
2236 33
2253 28
2256 61
2259 45
2268 7
2279 15
2282 58
2284 8
2299 27
2299 47
2303 23
2314 7
2323 45
2327 58
2329 29
2346 45
2347 27
2353 58
2362 30
2368 45
2377 35
2381 61
2386 15
2393 9
2402 18
2408 7
2410 47
2423 19
2430 52
2450 46
2452 58
2471 15
2473 69
2490 45
2500 22
2508 45
2521 18
2527 17
2546 18
2550 56
2567 58
2570 54
2593 58
2594 19
2614 19
2614 48
2635 18
2636 45
2654 15
2656 69
2672 51
2681 58
2690 15
2702 20
2708 16
2723 63
2727 51
2747 18
2747 50
2768 66
2771 15
2789 17
2789 20
2807 19
2813 58
2829 56
2839 75
2851 47
2860 67
2872 45
2881 71
2891 51
2902 18
2910 15
2928 45
2929 18
2948 45
2955 62
2970 49
2976 59
2997 18
3022 24
3044 23
3069 60
3098 68
3127 21
3153 61
3178 58
3205 72
3229 59
3254 60
3282 64
3303 58
3324 18
3350 61
3376 58
3402 64
3423 18
3452 22
3473 20
3494 60
Obtain the text data file appropriate to your section. You should save it and edit the file to remove the html tags. The file should look like a list of arrival times of requests and the time the server requires to process the request. Both of these times are in milliseconds.
Suppose the first few lines in the editted file are:
0 11
18 74
29 20
In a single threaded server: at 0 ms a request requiring 11 ms of processing arrives; the next request arrives at 18 ms and requires 74 ms to process; the third request arrives at 29 ms but cannot be started until the second request is finished. This results in a total time to process the three requests is 112 ms and average requests per second is 26.8 [(1/112)*1000].
In a two threaded server: at 0 ms a request requiring 11 ms of processing arrives; the next request arrives at 18 ms and requires 74 ms to process; the third request arrives at 29 ms and causes a second thread to start processing the request for 20 ms. The total processing time is 92 ms for the three requests and an average requests per second of 32.6 [(3/92)*1000].
Additional threads would not result in a better requests per second value. Therefore for this (admittedly small) input set the optimum number of threads is 2.
0 15
10 18
15 7
19 7
21 69
24 47
37 27
42 62
43 19
56 27
63 15
65 75
71 33
81 47
86 7
89 68
101 7
105 47
112 18
119 27
123 16
133 18
134 7
141 15
150 29
157 18
165 27
165 48
180 27
183 45
184 58
198 28
205 48
208 65
213 8
226 19
230 7
236 71
246 28
249 59
257 18
265 27
267 15
280 9
286 68
290 15
299 7
307 69
310 15
315 29
330 38
334 15
335 23
346 9
352 52
356 19
361 34
370 48
377 29
378 60
391 51
392 27
401 63
409 54
410 34
422 22
425 7
427 46
440 32
443 21
446 45
455 34
464 17
464 20
470 29
485 27
485 48
485 71
500 28
506 23
507 50
515 7
525 52
530 28
534 58
543 15
545 27
559 22
561 9
567 46
576 9
584 58
585 15
595 27
605 60
609 48
612 31
626 22
628 45
631 27
646 27
646 59
647 18
661 9
670 45
676 28
676 69
688 45
693 34
705 64
706 55
712 27
726 23
727 28
727 47
743 28
745 48
751 61
760 33
763 15
777 9
779 70
781 45
795 7
805 45
808 58
813 8
825 45
829 37
830 68
843 53
844 31
851 62
859 8
863 17
875 59
876 29
885 15
892 27
902 24
905 54
911 32
923 68
926 7
928 17
941 29
944 58
946 16
956 8
964 19
965 18
973 29
982 15
988 7
994 18
1004 31
1006 53
1015 18
1019 7
1024 49
1036 63
1038 7
1042 15
1053 9
1057 20
1065 46
1068 29
1078 18
1083 35
1083 49
1098 7
1100 19
1104 45
1116 28
1121 18
1126 55
1134 35
1142 18
1144 54
1149 7
1164 28
1165 15
1171 69
1179 8
1183 57
1194 27
1197 70
1201 18
1209 29
1218 21
1223 17
1227 7
1241 17
1245 30
1245 58
1260 45
1262 31
1267 62
1277 7
1283 55
1290 21
1292 7
1301 56
1309 29
1313 20
1319 18
1324 7
1334 67
1338 54
1339 32
1355 71
1357 31
1358 15
1372 30
1378 18
1380 48
1390 7
1398 18
1401 58
1407 7
1419 45
1422 61
1425 37
1439 55
1443 27
1443 63
1457 15
1458 7
1464 63
1473 7
1475 17
1485 61
1492 28
1494 53
1506 23
1507 29
1512 17
1525 31
1529 58
1531 15
1540 7
1550 70
1555 31
1555 45
1570 35
1573 15
1573 61
1589 27
1591 15
1602 69
1604 7
1612 15
1621 9
1623 21
1631 55
1636 7
1644 18
1649 15
1653 27
1667 56
1671 7
1672 24
1685 47
1686 27
1693 24
1701 29
1703 15
1718 31
1720 59
1724 55
1733 9
1744 15
1745 58
1749 27
1762 53
1766 29
1766 66
1781 34
1784 54
1787 63
1796 27
1806 19
1808 23
1811 7
1826 7
1829 16
1829 19
1843 30
1847 46
1850 18
1861 29
1865 56
1875 58
1879 31
1883 17
1894 8
1896 18
1901 19
1909 27
1920 50
1923 22
1928 8
1942 45
1943 27
1944 20
1958 7
1966 54
1971 20
1973 27
1988 7
1990 15
1996 65
2006 27
2012 18
2024 28
2025 22
2030 47
2043 27
2046 18
2048 47
2060 9
2066 16
2067 71
2075 34
2084 45
2088 24
2090 27
2106 15
2106 9
2113 60
2123 29
2126 19
2134 22
2142 7
2144 45
2155 60
2160 7
2162 17
2175 27
2181 15
2184 58
2190 33
2199 60
2206 29
2208 58
2217 45
2221 7
2235 53
2235 72
2236 33
2253 28
2256 61
2259 45
2268 7
2279 15
2282 58
2284 8
2299 27
2299 47
2303 23
2314 7
2323 45
2327 58
2329 29
2346 45
2347 27
2353 58
2362 30
2368 45
2377 35
2381 61
2386 15
2393 9
2402 18
2408 7
2410 47
2423 19
2430 52
2450 46
2452 58
2471 15
2473 69
2490 45
2500 22
2508 45
2521 18
2527 17
2546 18
2550 56
2567 58
2570 54
2593 58
2594 19
2614 19
2614 48
2635 18
2636 45
2654 15
2656 69
2672 51
2681 58
2690 15
2702 20
2708 16
2723 63
2727 51
2747 18
2747 50
2768 66
2771 15
2789 17
2789 20
2807 19
2813 58
2829 56
2839 75
2851 47
2860 67
2872 45
2881 71
2891 51
2902 18
2910 15
2928 45
2929 18
2948 45
2955 62
2970 49
2976 59
2997 18
3022 24
3044 23
3069 60
3098 68
3127 21
3153 61
3178 58
3205 72
3229 59
3254 60
3282 64
3303 58
3324 18
3350 61
3376 58
3402 64
3423 18
3452 22
3473 20
3494 60
u wan the algorithm to calculate the total average time?
I think I understand the problem. It can be spilt into two parts.
Given N "timestrips" (N is the number sample) of samples we can pack one sample into each strip. This translates to N threads performing these tasks completly indepent. The average processing time is then sum[n=1..N](t(n) )/N. This is obviously the minimal average response time that can be obtained.
We can reuse two thread, if the strips do not overlap (e.g. the end time of the first event is lower then the start time of the second). This does not effect the average time, so N was not optimal.
The question is about the number Q that denotes the smallest number of threads for which the average procesing time is equal to the optimum result.
In means of strips: What is the minimum number of strips needed to put all samples on it without any overlapping. These kind of optimization is very like to be np-complete. This means that the computing time needed is growning exponenetially with N. Problems of this kinds are virtually unsolvable for large N.
The data here has several constraints that might help to find a good approximation. I would try to map to strips starting with the largest processing time first on strips. Thereby put as many samples on the first strip as possible. Start a new strip only if there is no strip already created that fits the next strip. The resulting number of strips (after all samples have been allocated) P is >= Q.
Given N "timestrips" (N is the number sample) of samples we can pack one sample into each strip. This translates to N threads performing these tasks completly indepent. The average processing time is then sum[n=1..N](t(n) )/N. This is obviously the minimal average response time that can be obtained.
We can reuse two thread, if the strips do not overlap (e.g. the end time of the first event is lower then the start time of the second). This does not effect the average time, so N was not optimal.
The question is about the number Q that denotes the smallest number of threads for which the average procesing time is equal to the optimum result.
In means of strips: What is the minimum number of strips needed to put all samples on it without any overlapping. These kind of optimization is very like to be np-complete. This means that the computing time needed is growning exponenetially with N. Problems of this kinds are virtually unsolvable for large N.
The data here has several constraints that might help to find a good approximation. I would try to map to strips starting with the largest processing time first on strips. Thereby put as many samples on the first strip as possible. Start a new strip only if there is no strip already created that fits the next strip. The resulting number of strips (after all samples have been allocated) P is >= Q.
I implemented the alogrithm sketched above:
Least bound:5(15222,3554)
... need 5 CPU to perform 15222ms of work in 3554ms
48 strips for 450 samples
A good guess might to divide the running time by the time for the longest request. this gives 3554/85 = 42.
Another good lower bound is the maximum overlapping of the request. I calculated the for your sample to 17. I guess that the solution is close to this number, but as mentioned before it is hard to calculate.
Least bound:5(15222,3554)
... need 5 CPU to perform 15222ms of work in 3554ms
48 strips for 450 samples
A good guess might to divide the running time by the time for the longest request. this gives 3554/85 = 42.
Another good lower bound is the maximum overlapping of the request. I calculated the for your sample to 17. I guess that the solution is close to this number, but as mentioned before it is hard to calculate.
There has been an error in my code for calculation the maximum overlap (max. parallel threads)
// maximum overlap
int max = 0;
for (int nn = 0; nn< samples.size();nn++)
{
Request r0 = (Request) samples.get(nn);
int jj = r0.start;
int ovlc=0;
for (int ii = 0; ii< samples.size();ii++)
{
Request r1 = (Request) samples.get(ii);
if ( r1.start <= jj && r1.end> jj ) ovlc++;
if (ovlc>max) {
max=ovlc;
}
}
}
System.out.println("Max. overlap:"+max);
calculates for your sample data (at 863ms) 9 parallel threads. This seems to be the optimal solution too. I haven't proved it, but the argument is as follows: Take the threads the occur at maximum overlap P. Now take any other set of threads. These threads overlap at most P times. p of these P threads might overlap with the thread of the maximum, but the are no more than P-p overlaps, otherwise P was not the maximum overlap. The argument should be extendable to the rest of threads to prove that P threads are sufficient.
// maximum overlap
int max = 0;
for (int nn = 0; nn< samples.size();nn++)
{
Request r0 = (Request) samples.get(nn);
int jj = r0.start;
int ovlc=0;
for (int ii = 0; ii< samples.size();ii++)
{
Request r1 = (Request) samples.get(ii);
if ( r1.start <= jj && r1.end> jj ) ovlc++;
if (ovlc>max) {
max=ovlc;
}
}
}
System.out.println("Max. overlap:"+max);
calculates for your sample data (at 863ms) 9 parallel threads. This seems to be the optimal solution too. I haven't proved it, but the argument is as follows: Take the threads the occur at maximum overlap P. Now take any other set of threads. These threads overlap at most P times. p of these P threads might overlap with the thread of the maximum, but the are no more than P-p overlaps, otherwise P was not the maximum overlap. The argument should be extendable to the rest of threads to prove that P threads are sufficient.
kshireesh:
This old question needs to be finalized -- accept an answer, split points, or get a refund. For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations! No comment means you don't care.
This old question needs to be finalized -- accept an answer, split points, or get a refund. For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations! No comment means you don't care.
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:
- PAQ'd and points NOT refunded
Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
Venabili
EE Cleanup Volunteer
I will leave a recommendation in the Cleanup topic area that this question is:
- PAQ'd and points NOT refunded
Please leave any comments here within the next seven days.
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
Venabili
EE Cleanup Volunteer
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.