## 5 The PMOD Scheduler
### Pipelined Scheduling  
Our pipelined approach divides the overall scheduling into three stages: (a) the transferring stage, (b) processing stage and (c) packing stage. The transferring stage is the stage at which data streams are forwarded according to the communicating steps defined by the \(SM\). The maximum communication cost step is \(u\) and the remaining costs are \(<u\). The transferring stage employs all the hardware necessary to forward the streams among the system's nodes. The processing stage is the stage at which the streams are processed by the nodes. Here, we assume that all processing is implemented in constant time \(v\), as we assume that all the streams are of equal size. The processing stage involves all the hardware installed in the system's nodes, which is used for processing (processors, RAM, etc.). Finally, the packing stage is the stage at which the resulting processed streams are put into buffers in order to be forwarded to the next nodes for further processing. The hardware involved is each node's buffer; this is the fastest stage. We assume that the packing time, \(w\), is equal for all the streams being processed. In the analysis that follows, we will examine two cases:  
\[u > v>w \tag{12}\] \[v > u>w \tag{13}\]  
**(A) Some communication steps are more expensive compared to the stream processing; \(\mathbf{u}>\mathbf{v}>\mathbf{w}\). **  
In this first case, we assume that the maximum cost of transfer, \(u\), is larger than the processing cost \(v\). The packing cost is always considered the minimum among the three costs. As indicated by the \(SM\), which was presented is Section 5.1, the transferring costs are not the same for the communicating steps. Here, we describe a general case in which some of the communication steps are more expensive than their processing, while others are not; that is, their processing stage is more expensive. We will use Figure 2 to describe this case. The time is shown in the horizontal axis; some time values have been placed in the bottom of the figure due to space limitations. The horizontal axis shows the three pipeline stages. The grey areas indicate pipeline stage stalls; that is, a stage has no work to do and waits until it becomes busy again. For example, the processing stage cannot be active between times 0 and \(u\), as no data streams have arrived to the proper processing nodes. Notice that there are two communicating steps, \(S_{0},S_{1}\), with a maximum cost of \(u\), which is always the case. Since \(u>v\), one can easily see that the streams corresponding to these steps would be transferred in \(2u\) time, while their processing will have finished at time \(2u+v\). The next two steps, \(S_{2},S_{3}\), require a time of \(\theta\), where \(\theta<u\), but \(\theta>v\). Thus, their cost is still larger compared to the cost of the processing stage. This means that their transfer would be completed at times \(2u+\theta\) and \(2u+2\theta\), respectively, while their processing will have finished at times \(2u+\theta+v\) and \(2u+2\theta+v\), respectively. So far, it can be observed that the processing times are somehow \"absorbed\" by the transferring times. However, this is not the case for the communication steps, \(S_{4},S_{5}\), which require \(\chi\) and \(\psi\) time, where \(v>\chi>\psi\). Therefore, one can notice that the transfer stage for \(S_{4}\) and the processing stage for \(S_{3}\) start at time \(2u+2\theta\), but the streams of \(S_{4}\) would be transferred by \(2u+2\theta+\chi\), while the processing of \(S_{3}\), which started simultaneously, ends later, at time \(2u+2\theta+v\). Finally, the streams of \(S_{5}\) will be transferred by \(2u+2\theta+\chi+\psi\), and during that time, the processing of \(S_{4}\) streams takes place. The overall processing terminates at time \(2u+2\theta+\chi+\psi+v\). As can be observed, the packing times are totally \"absorbed\" (overlapped with the times required by the other stages), with the packing of \(S_{5}\) being the only exception.