Computing the strong components of a directed graph is an essential operation for a basic structural analysis of it. This problem can be solved by twice running a depth-first search (DFS). In an external setting, in which all data can no longer be stored in the main memory, the DFS problem is unsolved so far. Assuming that node-related data can be stored internally, semi-external computing does not make the problem substantially easier. Considering the definite need to analyze very large graphs, we have developed a set of heuristics which together allow the performance of semi-external DFS for directed graphs in practice. The heuristics have been applied to graphs with very different graph properties, including "web graphs" as described in the most recent literature and some large call graphs from ATT. Depending on the graph structure, the program is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.

This paper describes a scheme to implement a shared address space of size m on an n-node mesh, with m polynomial in n, where each mesh node hosts a processor and a memory module. At the core of the simulation is a hierarchical memory organization scheme (HMOS), which governs the distribution of the shared variables, each replicated into multiple copies, among the memory modules, through a cascade of bipartite graphs. Based on the expansion properties of such graphs, we devise a protocol that accesses any n-tuple of shared variables in worst-case time $O(n^{1/2+\eta})$, for any constant $\eta > 0$, using $O(1/\eta^{1.59})$ copies per variable, or in worst-case time O(n 1/2 log n), using O(log 1.59 n ) copies per variable. In both cases the access time is close to the natural $O(\sqrt{n})$ lower bound imposed by the network diameter. A key feature of the scheme is that it can be made fully constructive when m is not too large, thus providing in this case the first efficient, constructive, deterministic scheme in the literature for bounded-degree processor networks. For larger memory sizes, the scheme relies solely on a nonconstructive graph of weak expansion. Finally, the scheme can be efficiently ported to other architectures, as long as they exhibit certain structural properties. In the paper we discuss the porting to multidimensional meshes and to the pruned butterfly, an area-universal network which is a variant of the fat-tree.

In all recent near-optimal sorting algorithms for meshes, the packets are sorted with respect to some snake-like indexing. In this paper we present deterministic algorithms for sorting with respect to the more natural row-major indexing. For 1-1 sorting on an n × n mesh, we give an algorithm that runs in 2 · n + o(n) steps, matching the distance bound, with maximal queue size five. It is considerably simpler than earlier algorithms. Another algorithm performs k-k sorting in k · n / 2 + o(k · n) steps, matching the bisection bound. Furthermore, we present uniaxial algorithms for row-major sorting. We show that 1-1 sorting can be performed in $2 \frac{1}{2} · n + o(n) steps. Alternatively, this problem is solved with maximal queue size five in $4 \frac{1}{3} · n steps, without any additional terms.

Algorithms for performing gossiping on one- and higher-dimensional meshes are presented. As a routing model, the practically important wormhole routing is assumed. We especially focus on the trade-off between the start-up time and the transmission time. For one-dimensional arrays and rings, we give a novel lower bound and an asymptotically optimal gossiping algorithm for all choices of the parameters involved. For two-dimensional meshes and tori, a simple algorithm composed of one-dimensional phases is presented. For an important range of packet and mesh sizes, it gives clear improvements upon previously developed algorithms. The algorithm is analyzed theoretically and the achieved improvements are also convincingly demonstrated by simulations, as well as an implementation on the Paragon. On the Paragon, our algorithm even outperforms the gossiping routine provided in the NX message-passing library. For higher-dimensional meshes, we give algorithms which are based on an interesting generalization of the notion of a diagonal. These algorithms are analyzed theoretically, as well as by simulation.

An earlier parallel list ranking algorithm performs well for problem sizes $N$ that are extremely large in comparison to the number of PUs $P$. However, no existing algorithm gives good performance for reasonable loads. We present a novel family of algorithms, that achieve a better trade-off between the number of start-ups and the routing volume. We have implemented them on an Intel Paragon, and they turn out to considerably outperform all earlier algorithms: with $P = 2$ the sequential algorithm is already beaten for $N = \mbox{25,000}$; for $P = 100$ and $N = 10^7$, the speed-up is 21, and for $N = 10^8$ it even reaches 30. A modification of one of our algorithms solves a theoretical question: we show that on one-dimensional processor arrays, list ranking can be solved with a number of steps equal to the diameter of the network.

We present a constructive deterministic simulation of a PRAM with n processors and m = n α shared variables, 1 < α ≤ 2, on an n-node mesh-connected computer where each node hosts a processor and a memory module. At the core of the simulation is a Hierarchical Memory Organization Scheme (HMOS) that governs the distribution of the PRAM variables (each replicated into a number of copies) among the modules. The HMOS consists of a cascade of explicit bipartite graphs whose expansion properties, combined with suitable access and routing protocols, yield a time performance that, for α < 3/2, is close to the Ω(√n) bound imposed by the network's diameter, and that, for α ≥ 3/2, is a function of α never exceeding O(n5/8).

Article Matching the bisection bound for routing and sorting on the mesh Share on Authors: Michael Kaufmann View Profile , Sanguthevar Rajasekaran View Profile , Jop F. Sibeyn View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 31–40https://doi.org/10.1145/140901.140905Published:01 June 1992 30citation197DownloadsMetricsTotal Citations30Total Downloads197Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access