A strongly connected component (SCC) of a digraph is a maximal subgraph G' such that for every two nodes u, v in G' there is a path from u to v and a path from v to u in G'.

The sequential algorithms for strongly connected components are based on DFS which is difficult to parallelize. In STAPL we begin with a work sub-optimal sequential algorithm that exposes more parallelism( Lisa Fleischer , Bruce Hendrickson , Ali Pinar, On Identifying Strongly Connected Components in Parallel, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.505-511, May 01-05, 2000)

STAPL's pSCC algorithm starts by trimming the input graph of vertices that are not part of a strongly connected component. After that a pivot is chosen and we mark all vertices accesible from the pivot forward and bacward. A strongly connected component will be the nodes that are marked both forward and backward(see the pseudocode and the figure below).

  pSCC(G)
  If G is empty then return
  trim() G in forward direction
    //topological_traversal with vertices of indegree zero as
    //starting points
  If G is not empty then
	trim() G in backward direction //topological_traversal
	select pivot V from the live vertices
	mark Pred(G,v) and Succ(G,v) //parallel_bfs traversal
	SCC(G,v) = Pred(G,v)  /\   Succ(G,v)
	do in parallel
		pSCC(Pred(G,v)-SCC(G,v))
		pSCC(Succ(G,v)-SCC(G,v))
		pSCC(Rem(G,v))
  endif

The algorithm is input dependent, the number of iterations in the loop beeing proportional to the number of SCCs in the input pGraph. Below we include a graph with the algorithm performance on a 16 processor HP V2200. The graph presents also the effect of messages aggregation done automatically by ARMI.

William McLendon, Bruce Hendrickson, Steve Plimpton, Lawrence Rauchwerger, "Finding Strongly Connected Components in Parallel in Particle Transport Sweeps," In Proc. ACM Symp. Par. Alg. Arch. (SPAA), pp. 328-329, Crete, Greece, Jul 2001.
Proceedings(ps, pdf, abstract)

If you have questions about STAPL, please email stapl-support@tamu.edu

Parasol Home | Research | People | General info | Seminars | Resources   Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science Engineering TAMU