## 5 The PMOD Scheduler
### Putting the Ideas Together  
In this paragraph, we combine all of the ideas discussed in this section to present the method of implementing the PMOD scheduler (see Algorithm 1). Initially, the system parameters \(N,t\) are set and read (line 2), and the two distributions, the initial \(R\) and the next \(R^{\prime}\), are defined (line 3). Then, the communication classes are computed based on the parameters of \(R,R^{\prime}\). To define the communication steps, the scheduler implements the two communication steps described in detail in Section 5.1 so that the class table is transformed into a scheduling matrix (lines 5-10). Then, the application DAG (line 12) is read and the proper communications between the spouts/bolts are defined (application specific). To pipeline the overall processing, the system's hardware is set to execute three different procedures simultaneously (line 13): implementing the communications defined in one step, processing the data associated to a communicating step and packing the newly processed data for future transfer/processing. The system starts from step \(k=0\), as defined by the scheduler. The communications between the node pairs defined in this step are implemented. Now, if \(k=0\), stage S2 has no work to do (line 21); the same holds for stage S3 (line 22). Then, \(k\) is incremented by one (line 23), so the three stages are set to work again. Stage 1 implements communication step 1, and stage S2 (\(k=1>0\)) implements the processing of the data associated with the previous stage S1 (step 0). The last stage, S2, remains idle, since \(k<2\). Once \(k\) is incremented again, stage S1 will work on the transmission of data associated  
Figure 3: Pipelined scheduling, \(v>u>w\). with communication step 2, while stage S2 will process the data associated with communication step 1 and stage S2 will pack the data associated with communication step 0. This procedure continues until all the communications have been implemented. If more streams are left unprocessed, \(k\) is set back to 0 (the program moves back to line 15) and the repeat block is executed once again. The complexity of the PMOD scheduler is clearly linear, as it depends on the number of transformations required to change the CT into a single index matrix (SIM) and then the SIM into the scheduling matrix, \(SM\). As the number of these transformations is determined by the number of nodes in the system, PMOD's complexity is \(O(N)\). ```
input :An application graph organized in spouts/bolts of \(t\) tasks  A cluster of \(N\) nodes  Changes in \(t\) or \(N\) or both, during runtime output :A dynamic pipelined scheduler, \(PMOD\), with reduced overall cost
1 begin
2 Read parameter changes, that is, new values of \(t\) and \(N\)  Define the distributions \(R(i,n,L,x)\) and \(R^{\prime}(j,q,M,y)\)  Solve Equation (9) to Find all the classes \(k\) and produce the Class Table (CT) //Step 1: Transform CT into a Single Index Matrix (SIM) For each node pair \((n,q)\) in row \(k\), place the \(q\) value to columnn  end For // Step 2: Mix Class Elements to Produce the Scheduling Matrix (SM)  Interchange \(\alpha\) elements of homogeneous classes, that reside in corresponding columns. The rows of the \(SM\) correspond to communicating steps between the system's nodes
3 Read the application DAG and define all the communications between components. Define the three pipeline stages (transferring, processing, and packing) \(k=0\) // Organize the three operations in a pipeline fashion: Repeat // Stages S1-S2 are simultaneous and correspond to transferring, processing, packing: S1. Let the transferring stage hardware implement communication step \(k\) S2. If \(k>0\), let the processing stage hardware process the data from step \(k-1\) S3. If \(k>1\), let the packing stage hardware pack data from step \(k-2\) Increment \(k\) by one and repeat the simultaneous stages S1-S3. Until all the communications from \(k\) communication steps are implemented. If more streams are left unprocessed, go to line 15 and re-execute the pipeline stages.