From kumar@cs.unc.edu Fri May 27 13:36:48 1994 Date: Thu, 26 May 94 18:36:18 -0400 From: Subodh Kumar To: challeng@dimacs.rutgers.edu, prins@cs.unc.edu Subject: Progress Report Cc: goddard@cs.unc.edu \documentstyle[12pt]{article} \setlength{\topmargin}{-.5in} \addtolength{\textheight}{1.5in} \addtolength{\textwidth}{\evensidemargin} \addtolength{\textwidth}{\oddsidemargin} \setlength{\oddsidemargin}{.25in} \setlength{\evensidemargin}{.25in} \addtolength{\textwidth}{-1.0\oddsidemargin} \addtolength{\textwidth}{-1.0\evensidemargin} \begin{document} \setlength{\baselineskip}{20pt} \newcommand{\comment}[1]{} \title{ Communication Based Mapping of Graph Algorithms\\ to Meshes \\ } \author{Subodh Kumar \and Jan Prins \and Stephen Goddard} \maketitle \section{Introduction} The simplified structure of PRAMs makes writing parallel programs and reasoning about their correctness very easy. The caveat is that most real life parallel machines are far from PRAMs. The costs of operations assumed in PRAMs are unrealistic. In particular, the ability to read any memory location translates to arbitrary routing, and possibly collisions, on most machines. These generally have high cost and lead to disappointing performance. On the other hand, for specific communication topology certain patterns of communications can be much less costly. For example, on a mesh connected machine, like the MasPar MP-1/MP-2, communication within a row or a column can be done efficiently. We are investigating parallel algorithms for determining connected components in undirected graphs, and their implementation on mesh-connected computers. While there exist a variety of PRAM algorithms for these problems, some do no really require arbitrary routing. We are experimenting with ways to decompose the data structures used in the algorithms such that any information that a given processor needs can be found either in its row or in its column. Thus, rather than designing the implementation directly for the mesh, our strategy is to start with a PRAM algorithm (e.g.~Algorithm $5.1$ in \cite{Jaja}) and map it to the mesh to minimize the communication time and thus speed up the total execution. This new algorithm (call it {\bf A1}) represents the graph as an adjacency matrix and stores $\frac{n^2}{p}$ elements per processor, $n$ being the number of vertices in the graph and $p$ the number of processors on the machine. Clearly, it has bad load balancing and memory utilization characteristics and performs excessive work on sparse graphs. The work complexity of {\bf A1} is $O(n^2\log n)$ and it works well only on dense graphs. {\bf A1} is our ``first level'' algorithm and we plan to derive from it, a sequence of algorithms with increasing work efficiency, $O(m\log n)$ being the goal ($m$ is the number of edges in the graph). So the next question is, can we modify it without destroying the communication structure so that sparse graphs also are efficiently handled. Investigating the principles behind such modification is a major component of this effort. Till now we have only got till {\bf A2}, which does not keep the complete adjacency matrix on the processors. It can handle much larger graphs than {\bf A1} and is more work efficient. {\bf A2} stores only the edges that are present in the graph. The edges are cyclically allotted to processors and hence can cause some load imbalance. The work complexity of this algorithm, when the imbalance is not high, is $O(n~d\log n)$, where $d$ is the maximum degree of a node. \section{Status} {\bf A1} is based on the idea of grafting (Algorithm $5.1$ in \cite{Jaja}). Since it uses the adjacency matrix representation, it can be adapted to use only row/column communication. We have implemented this on a MasPar MP-1. In principle, it works by updating rooted stars at each iteration, starting with single node stars represented by vertices of the graph. Each single node star is assigned an id equal to the id of its vertex. At each iteration, if a there lies an edge between two stars, the star with the higher id is hooked onto the star with the lower id, and all structures are compressed into stars again by pointer jumping. If a vertex leaves id1 and hooks onto id2, all the vertices in the star id1 are hooked onto id2. If there are more than one such id2's, the minimum is selected. The corresponding virtualized pseudocode follows: \pagebreak \noindent {\bf LOOP} \indent\hspace{0.25in} \begin{minipage}{5in} \begin{enumerate} \item Find the processor with the minimum id (i.e.~the processor holding the vertex with the minimum id) that has a '1' in the adjacency matrix at its position. This minimum is a scan operation collects in the top row of the mesh. \item Broadcast this minimum id down the column, so the winning processor knows that it has won. \item The winning processor broadcasts its new id to its column -- this achieves one step of pointer jumping. \item The diagonal processors, which have the old id corresponding to the winning processor, send that information to the winning processor (in their column). \item The new ids are now scanned in their respective rows by the processors that were responsible for the change, and another min operation picks the new id's for each row, which is then broadcast across the row.\\ \end{enumerate} \end{minipage} \noindent {\bf WHILE any processor changed its id}. The algorithm executes this loop no more than $\log n$ times. Note that all scan and broadcast operations are restricted to just rows or just columns. We have also implemented some known algorithms from \cite{Jaja} and \cite{Gri} in both MPL and NESL for comparison, and have got encouraging results. \section{Plan} We are currently working on an algorithms that will have a complexity of $O(n~d\log n)$ for all, or at least most, graphs. We believe this can be done without adding any significant overhead. The next step is to aim for the best known PRAM complexity of $O(m \log n)$. We expect this will add a significant overhead to our algorithm, but will still be fast enough for a large class of graphs. Once we have a suite of algorithms, including those that are being implemented by the other groups, we hope we can empirically define the class of graphs -- most likely based only on the sparsity, $\frac{m}{n^2}$ -- on which a given algorithm works better than the others. Then, given an input graph, we can sample its connectivity and choose to run the algorithm expected to perform the best on that instance. We are hoping we can gain access to a MasPar MP-2, so that we can get a wider range of implementation figures. Once we have all the implementation, we can start analyzing the losses and gains. We hope to quantify the benefits over arbitrary routing. We do not have a suit of benchmarks yet. In consultation with the other groups, we hope we will be able to decide on some meaningful graphs. \bibliographystyle{alpha} %\bibliography{references}. \begin{thebibliography}{ABLP89} \bibitem[JG]{Gri} John~Greiner. \newblock A Comparison of Data-Parallel Algorithms for Connected Components. \newblock CMU Technical Report CMU-CS-93-191 \bibitem[JJ]{Jaja} Joseph~J\'{a}j\'{a}. \newblock {\em Parallel Algorithms}. \newblock Addison Wesley, NewYork, 1992. \end{thebibliography} \end{document}