does any body know what algorithum for the data given below?

kshireesh
kshireesh used Ask the Experts™
on
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
 

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
u wan the algorithm to calculate the total average time?

Commented:
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.  

Commented:
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.
Exploring SQL Server 2016: Fundamentals

Learn the fundamentals of Microsoft SQL Server, a relational database management system that stores and retrieves data when requested by other software applications.

Commented:
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.
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.

Commented:
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
Force accepted

** Mindphaser - Community Support Moderator **

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial