# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 1 Introduction  
For many years, parallel and distributed networked computer systems have been developed and implemented to tackle compound scientific problems powerfully. Many parallel and distributed systems have been designed to change the distribution of an array at run-time to improve the desired performance. At that time, each processor needs to know which local elements of the array should be sent to the specified processor, and which elements of the array should be received from the specified processor. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. The former is used in the SCALAPACK library, which uses the block-cyclic data distribution on a virtual grid of processors to reach load-balance on arrays, and adopts equal memory usage between processors [1; 2]. On the other hand, an irregular distribution does not adopt specific rules or methods to represent the desired decomposition. Instead, they usually represent the irregular array distribution with the help of user-defined command or procedures. As an example, High Performance Fortran version 2 (HPF2) supports a generalized block distribution (named GEN_BLOCK) format [3; 4], when unevenly sized data of an array is to be allocated to a set of processors. For example, a regular data redistribution using Block-Cyclic(\(\alpha\)) to Block-Cyclic(\(\beta\)) (from \(P\) processors to \(Q\) processors) (denoted by \(BC(\alpha,\,\beta,\,P,\,Q)\)) can be modeled by a bipartite graph \(G_{BC(\alpha,\,\beta,\,P,\,Q)}=(X,\,Y,\,E)\), where \(X=\{x_{0},\,x_{1},\,\ldots,\,x_{|X|-1}\}\) and \(\mathrm{Y}=\{y_{0},\,y_{1},\,\ldots,\,y_{|Y|-1}\}\) represent source processor set \(\{p_{0},\,p_{1},\,\ldots,\,p_{|X|-1}\}\) and destination processor set \(\{p_{0},\,p_{1},\,\ldots,\,p_{|Y|-1}\}\), respectively. In \(G_{BC}\) (\(\alpha,\,\beta,\,P,\,Q\)if the source processor \(p_{i}\) wants to send \(c\) elements of the array to the destination processor \(p_{j}\), we add an edge (\(x_{i}\), \(y_{j}\)) to \(E\) with a weight \(c\). For simplicity, in this work, a shorter symbol \(BC(\alpha,\beta,P)\) is used to represent \(BC(\alpha,\beta,P,P)\). In Figure 1, a data redistribution pattern \(BC(1,4,4)\) is depicted as an example, and its weighted distribution graph \(G_{BC}\)\((1,4,4)\) is also shown in Figure 2. In Figure 1, array elements A(1:16) mapped onto four processors (\(P\)) are to be redistributed to four (\(P\)) processors. In source distribution, every block with \(\alpha\)(=1) element are mapped onto one of processors which are ordered in the cyclic sequence. As a result, A(1), A(5), A(9), A(13) are mapped onto processor \(P_{0}\) in Figure 1. On the other hand, in target distribution, every block with \(\beta\)(=4) element are mapped onto one of the processors which are ordered in the cyclic sequence. Consequently, A(1), A(2), A(3), A(4) are mapped onto processor \(Q_{0}\) in the new distribution. Since A(1), A(2), A(3), A(4) are sent to \(Q_{0}\) by \(P_{0}\), \(P_{1}\), \(P_{2}\), \(P_{3}\), respectively, there are four edges connecting \(P_{0}\), \(P_{1}\), \(P_{2}\), \(P_{3}\) to \(Q_{0}\) in the distribution graph (Figure 2). In a similar way, an irregular distribution \(GB\)\((P,Q)\) is modeled by a weighted bipartite graph \(G_{GB(P,Q)}=(S,T,E)\). For instance, in Figure 3, array elements A(1:100) are to be redistributed. Originally, array elements A(1:24), A(25:50), A(51:64), A(65:100) are mapped onto \(P_{0}\), \(P_{1}\), \(P_{2}\), and \(P_{3}\), respectively. After redistribution, a new distribution is formed, such as A(1:15), A(16:49), A(50:89), A(90:100) onto \(Q_{0}\), \(Q_{1}\), \(Q_{2}\), and \(Q_{3}\), respectively. Its distribution graph, \(G_{GB(4,4)}\), is presented in Figure 4. Note that one processor may need to send array elements to multiple consecutive processors in an irregular distribution. For example, \(P_{0}\) has 24 elements A(1:24) which A(1:15) are sent to \(Q_{0}\), and A(16:24) are sent to \(Q_{1}\).