# Calculating parallel program's execution time

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.

• "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? – James Arathoon Jul 5 '18 at 12:26
• @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. – pokemarine Jul 5 '18 at 12:37
• Then you should write 'The server will only give out a new job if the currently running job count is smaller than m.' – James Arathoon Jul 5 '18 at 12:52
• 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. – James Arathoon Jul 5 '18 at 13:05
• @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). – pokemarine Jul 5 '18 at 13:55

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.