# New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling
## 3 Related Work  
Regular data redistribution like the SCALAPACK library uses block-cyclic data distribution on a virtual grid of processors to achieve good load-balance on arrays and an equal memory usage between processors. Arrays are wrapped by blocks in all dimensions corresponding to the processor grid. Many algorithms and formulism for discussing regular array redistribution are classified into two types: (1) set identification; and (2) communication optimization. [PERSON] et al. found a mathematical representation for redistribution, which belongs to the former [19]. [PERSON] et al. implemented their algorithm in the ScaLAPACK so as to go from a block cyclic distribution to another one [20]. Based on a generalized matrix formula, [PERSON] et al. devised an algorithm for array redistribution from cyclic(x) on source processors to cyclic(Kx) on destination processors [1]. [PERSON] et al. proposed various redistribution methods in BLOCK-CYCLIC fashion for a very special application which executed block-partitioned linear algebra algorithms on dense matrices [2]. [PERSON] et al. pointed out some characterizations of the sparse matrix redistribution and its related issues because of the use of compressed representations [21]. [PERSON] et al. proposed a new method to perform a BLOCK-CYCLIC array redistribution [22]. They also implemented the proposed method on an IBM SP2 parallel machine. The second type concerns communication optimization techniques, including processor mapping techniques for reducing transmission overheads [23; 24; 25], a multistage approach for decreasing startup \begin{table}
\begin{tabular}{c c} \hline
**Notations** & **Descriptions** \\ \hline \(n\) & the number of vertices in the input graph \(G\) \\ \(d_{G}(v)\) & the number of incident edges to vertex \(v\) in a graph \(G\) \\ \(L(G)\) & the line graph of \(G\) \\ \(N(v)\) & the set of vertices adjacent to vertex \(v\) \\ \(v(e)\) & the weight of edge \(e\) \\ \(\Delta(G)\) & the maximum degree of vertices of \(G\) \\ \(\omega(G)\) & the number of components of \(G\) \\ \(\chi^{\prime}(G)\) & the edge chromatic number of \(G\) \\ \(z\) & the number of used colors \\ \(G_{BC(a,\,\beta,\,P,\,Q)}\) & the distribution graph of BLOCK-SYCLIC array redistribution using Block-Cyclic(\(\alpha\)) to \\  & Block-Cyclic(\(\beta\)) (from \(P\) processors to \(Q\) processors) \\ \(G_{GB(P,\,Q)}\) & the distribution graph of GEN\_BLOCK redistribution from \(P\) processors to \(Q\) processors \\ \hline \end{tabular}
\end{table} 
Table 1: Notations used in this work. Figure 8: An interval graph. costs [26], scheduling algorithms for avoiding contention [14; 27; 28; 29], and a strip-mining method for reducing communication and computational overheads [30]. On the other hand, with respect to irregular array redistribution, previous work has usually focused on indexing, message generation, or communication efficiency. [PERSON] et al. first mentioned the problem of communication set generation for irregular applications [31]. They also devised optimization techniques for irregular array in nested loops. To decrease communication cost in GEN_BLOCK redistribution, [PERSON] et al. [25] devised logical processor reordering methods on irregular array redistribution. In [3; 4], [PERSON] et al. designed a divide-and-conquer approach to execute irregular array redistribution. In [14], [PERSON] et al. presented two-stage scheduling for relocation problems on a processor grid. Their proposed scheduling algorithm makes use of a spatial locality in message passing. Their algorithms have been implemented on CRAY T3E and IBM SP2. In [15], [PERSON] et al. presents an efficient algorithm to partition large messages into multiple small ones and schedules them by using the minimum number of steps without communication contention and, in doing so, reduces the overall redistribution time.