5
$\begingroup$

I am trying to calculate the probable execution time of a highly parallelizable program, where the execution's 70%-80% can run in parallel. I read about the topic, but mostly people mention simple situations, but I have another condition the parallelization have to abide.

A thread have to perform a specific job it gets from the server, which can be calculated as a best and worst case scenario's average (example.: best 500ms, worst 1500ms, then let's say a job's execution time we use to calculate is 1000ms) and there is an m number, which is a maximum number of jobs that can run in the same time. Meaning, even if I have 200 threads that can run jobs parallel, the server won't give out a job only if the number of currently running job count is smaller than m.

I would like to plot out a few graphs for myself for analysation purposes, but I don't know how to implement the smaller than m condition.

If I have 1 679 616 (36^4) number of jobs and one job would take 1000ms. One thread would take 19,44 days to complete all of them, if it can always take a job.

$\endgroup$
  • $\begingroup$ "the server won't give out a job only if the number of currently running job count is smaller than m". Is that what you meant to say? $\endgroup$ – James Arathoon Jul 5 '18 at 12:26
  • $\begingroup$ @JamesArathoon Basically I mean the server rate limits the requests and stops you from requesting more then the configured limit. For example, I could set it to a 100 jobs / 1 seconds. $\endgroup$ – pokemarine Jul 5 '18 at 12:37
  • $\begingroup$ Then you should write 'The server will only give out a new job if the currently running job count is smaller than m.' $\endgroup$ – James Arathoon Jul 5 '18 at 12:52
  • $\begingroup$ If I understand what you are saying, then if $n$ is the number of parallel processors available, then setting $m > n$ has no effect. Setting $m \le n$ limits the number of processors that can be simultaneously used to $m$, rather than to $n$ the actual physical number of parallel processors available. $\endgroup$ – James Arathoon Jul 5 '18 at 13:05
  • $\begingroup$ @JamesArathoon Depends on the time interval, If I use a bigger time gap, like 50000 ms, it will reduce the number of executions per seconds drastically. (200 jobs / 1 seconds vs. 200 jobs / 50 seconds). In my question I choose the average job completion time as the time gap (1s). $\endgroup$ – pokemarine Jul 5 '18 at 13:55
1
+50
$\begingroup$

The main question: due to what the computing process can be braked, if the task is completely determined? Usually the reason is that there is a graph of the computational process that limits the possibilities of parallel execution of tasks.

In the model under consideration, the reason is to synchronize the tasks that are running in parallel. The probable meaning is that simultaneous loading of data into streams frees the server for asynchronous reception and processing of results.

If such a model is correct, then the server should wait for the completion of all tasks in the threads before synchronously issuing new tasks to the threads. Such synchronization is determined both by the number of tasks and by the distribution law of the random variable-the time $T$ of the task in the stream. The output requires an estimate of the completion time $\overline {T_m}$ of jobs in all $m$ threads and the associated parameters.

Let $$f(t, T, \Delta, 1)$$ is probability density function of probability distribution for one thread and $$f(t, T, \Delta, k)$$ is probability density function of probability distribution for $k$ threads. Then $$\overline {T_1} = \int\limits_{-\infty}^\infty xf(x,T,\Delta,1)\,\mathrm dx,$$ $$\overline {T_m} = \int\limits_{-\infty}^\infty xf(x,T,\Delta,m)\,\mathrm dx,$$ $$f(t, T, \Delta, k_1+k_2) = f(t,T,\Delta,k_1) g(t,T,\Delta,k_2)+f(t,T,\Delta,k_2) g(t,T,\Delta,k_1),$$ where $$g(t, T, \Delta, k) = \int\limits_{-\infty}^t f(x,T,\Delta,k)\mathrm dx.$$ For the homogenius distribution law, $$f(t,T,\Delta,1) = \dfrac1{2\Delta}u(t,T,\Delta),$$ where $$u(t,T,\Delta)= \begin{cases} 1,\text{ if } t\in[T-\Delta,T+\Delta]\\[4pt] 0,\text{ otherwise}, \end{cases}$$ $$g(t, T, \Delta, k) = \int\limits_{-\infty}^t f(x,T,\Delta,k)\mathrm dx = h(t-(T-\Delta))\int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,k)\mathrm dx,$$ where $$h(x)=\begin{cases} 1,\text{ if } x\ge0\\ 0,\text{ otherwise}. \end{cases}$$ In partial, $$f(t, T, \Delta, 2k) = 2f(t,T,\Delta,k) g(t,T,\Delta,k) = 2f(t,T,\Delta,k)\int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,k)\mathrm dx.$$ For example: $$f(t, T, \Delta, 2) = 2f(t,T,\Delta,1) \int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,1)\,\mathrm dx = u(t,T,\Delta)\dfrac{t-T+\Delta}{2\Delta^2}= \begin{cases} 0,\qquad\qquad\qquad \text { if } t<T-\Delta\\[4pt] \dfrac{t-T+\Delta}{2\Delta^2},\text{ if }t\in[T-\Delta,T+\Delta]\\[4pt] 0,\qquad\qquad\qquad \text{ if } t>T+\Delta, \end{cases}$$ $$\overline {T_2} = \int\limits_{T-\Delta}^{T+\Delta}x\dfrac{(x-T+\Delta)^2}{2\Delta^2}\,\mathrm dx=T+\dfrac13{\Delta},$$ $$f(t, T, \Delta, 4) = 2f(t,T,\Delta,2) \int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,2)\,\mathrm dx = u(t,T,\Delta)\dfrac{(t-T+\Delta)^3}{4\Delta^4},$$ $$\overline {T_4} = \int\limits_{T-\Delta}^{T+\Delta}x\dfrac{(x-T+\Delta)^3}{4\Delta^4}\,\mathrm dx=T+\dfrac35\Delta,$$ $$f(t, T, \Delta, 8) = 2f(t,T,\Delta,4) \int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,4)\,\mathrm dx = f(t,T,\Delta,1)\dfrac{(t-T+\Delta)^7}{32\Delta^8}$$ $$\overline {T_8} = \int\limits_{T-\Delta}^{T+\Delta}x\dfrac{(x-T+\Delta)^7}{32\Delta^8}\,\mathrm dx=T+\dfrac79\Delta,$$ $$f(t, T, \Delta, 16) = 2f(t,T,\Delta,8) \int\limits_{T-\Delta}^{\min(T+\Delta,t)} f(x,T,\Delta,8)\,\mathrm dx = f(t,T,\Delta,1)\dfrac{(t-T+\Delta)^{15}}{4096\Delta^{16}}$$ $$\overline {T_{16}} = \int\limits_{T-\Delta}^{T+\Delta}x\dfrac{(x-T+\Delta)^{15}}{4096\Delta^{16}}\,\mathrm dx=T+\dfrac{15}{17}\Delta,$$ etc.

$\endgroup$
  • $\begingroup$ I am struggling to implement this, Could you please give me an example? $\endgroup$ – pokemarine Jul 9 '18 at 6:08
  • $\begingroup$ @pokemarine See updated post. Waiting for comments. $\endgroup$ – Yuri Negometyanov Jul 9 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.