FG Theoretische Informatik
Many-core processors combine fast on-chip communication
with access to large amounts of shared memory. This
makes it possible to exploit the benefits of distributed as well
as shared memory programming models within single parallel
algorithms. While large amounts of data can be shared in the
memory and caches, coordinating the activities of hundreds
of cores relies on cross core communication mechanisms with
ultra low latency for very small messages. In this paper we
discuss two communication protocols for the Intel SCC and
compare them to the MPI implementation of the SCC. Our
micro-benchmark results underline that special purpose protocols
for small messages make much finer levels of parallelism possible
than general purpose message passing systems.
Index Terms—many-core, message passing, shared memory
Today's multi-cores and future many-cores are NUMA architectures with complex cache hierarchies and multiple memory channels. Depending on the topologies of these memory networks we find everything from true data sharing with shared caches to distributed memory architectures which just pretend to be physical shared memory systems. In fact, most many-cores are hybrid systems that exhibit the characteristics of both distributed systems and SMPs. In this paper we argue in favor of middleware platforms for many-cores. We will discuss the needed functionality in contrast to common distributed system middleware and present micro benchmarks on several architectures to substantiate our claims.
Modularity is a widely used quality measure for graph clusterings. Its exact maximization is prohibitively expensive for large graphs. Popular heuristics progressively merge clusters starting from singletons (coarsening), and optionally improve the resulting clustering by moving vertices between clusters (refinement). This paper experimentally compares existing and new heuristics of this type with respect to their effectiveness (achieved modularity) and runtime. For coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent multi-step algorithm is no improvement over simple single-step coarsening for these criteria. For refinement, a new multi-level algorithm produces significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature.