A Simple Problem
I was going through a parallel computing example when I encountered the scenario described here. Consider the analysis of patient MRI (Magnetic Resonance Imaging) scans. Assume that a MRI image is processed in three stages, namely initial, intermediate and final, and each stage of processing takes 7 minutes. In this case, there exists a dependency between each stage. In order to perform intermediate processing on the image, we first need to complete initial processing. And before performing final processing, intermediate processing should be complete. That is, the processing order of the stages should be followed.
Leveraging Benefits of Parallelism
If the above is done in a sequential manner, each image would take 21 minutes (3 stages with 7 minutes spent on each).
Assume the 3 computers (X, Y, and Z) are assigned to the above process group. Note that while X is processing an image, both Y and Z are idle. Assume 4 MRI images (img1, img2, img3, img4) needs to be processed. We can assign X to process the initial stage of img1 and Y to process the intermediate stage, and Z to process final stage of the same. This is called interleaving. Here we already have parallelism because while Y is processing the intermediate stage of img1, X is processing the initial stage of img2. Let us continue the above until all 4 images are completely processed. We will see that when Z is processing img1, X is processing img3. This overall process is called execution pipelining. How do we find how much time it would take to completely process all 4 images? Now comes simple imagination, first visualize the following.
After 7 minutes, initial processing of img1 will complete.
Then as time increases by another 7 minutes, the following becomes relevant.
After 14 minutes, intermediate processing of img1 and initial processing of img2 will complete.
What follows is a visualization of complete processing for each of the 3 stages of all 4 images.
After 42 minutes, processing for all stages of all images will complete.
Now finding the total time taken is as easy as counting the rows in above figure.
While visualizing the problem as above can be thought of as a simple task at some point in our learning, the thinking pattern involved deserves our attention, for thinking along such patterns can immensely help in understanding things we may otherwise find harder to grasp.