Dynamic Loop Scheduling

Self Scheduling:

• An idle processor requests for work.
• Master processor keeps record of available and assigned work.

Execution time

$$T_P=\frac{P}{N}(B+\sigma (N))$$

Speed up

$$S=\frac{T_s}{T_p}=\frac{PB}{P\sigma +\frac{PB}{N}}=\frac{B}{\sigma (N)+B/N}$$ $$\underset{N\to \infty }{\lim }S=\frac{B}{{\sigma }_{\infty }}$$

where,

• $P\to$ Number of work items to be distributed
• $N\to$ Available processors
• $B\to$ Average execution time of a work item
• $\sigma (N)\to$ Dispatch time of work item
  Replace P by N

Note: The dispatch time grows asymptotically with the number of parallel requests i.e. weak scaling

Chunk Scheduling

The overhead of self-scheduling can be reduced by chunking a fixed number of iterations $k$ together. Here $k$ is known as the chunk size. Execution Time

$$T_P=\frac{N}{k\cdot P}\left(k\cdot B+\sigma \left(P/k\right)\right)$$

Speed-up

$$\underset{p\to \infty }{\lim }S=\frac{k^{2}B}{{\sigma }_{\infty }}$$

Note: Chunk Scheduling is $k^2$ times faster than self scheduling.

Guided Self Scheduling

Here the Chunk size $k$ keeps varying. Usually starts with a larger chunk and gets smaller over time. The chunks are allotted based on available compute (idling processor). This method has better load balancing.