Refine
Year of publication
Document Type
Way of publication
- Open Access (1)
Language
- English (16)
Keywords
Institute
BTU
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.
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
On many-core processors, both operating system kernels and bare metal applications need efficient cross-core coordination and communication. Although explicit shared- memory programming and message passing might provide the best performance, they also limit the system’s control over scheduling. In contrast, interrupt-driven cross-core invocations provide universal coordination mechanisms that also enable preemptive operations across cores. This paper surveys cross- core invocation mechanisms and their usability with respect to prevalent coordination scenarios. We integrated some of these mechanisms into a bare-metal environment for the Intel SCC pro- cessor and will discuss implementation aspects of the interrupt- driven invocations. In conclusion, such invocation mechanisms provide an expressive platform for future operating systems kernels and bare-metal applications.
With the evolution toward fast networks of many-core processors, the design assumptions at the basis of software-level distributed shared memory (DSM) systems change considerably. But efficient DSMs are needed because they can significantly simplify the implementation of complex distributed algorithms. This paper discusses implications of the many-core evolution and derives a set of reusable elementary operations for future software DSMs. These elementary operations will help in exploring and evaluating new memory models and consistency protocols.
Many-core architectures trade single-thread performance for a larger number of cores. Scalable throughput can be attained only by a high degree of parallelism, minimized synchronization. Whilst this is achievable for many applications, the operating system still introduces bottlenecks through non-local sharing, synchronization,, message passing. A particular challenge for highly dynamic applications, for example invasive HPC applications, elastic compute clouds, is the management of short-living application threads, processes. This paper discusses OS architecture choices based on microkernel, multikernel, distributed systems designs, our development experience in the context of the MyThOS project. Initial experiments show a much faster thread creation, activation compared to monolithic systems like Linux while providing a more flexible protection, threading model that is better suited for dynamic scenarios. However, despite significant progress in the overall domain of operating systems, the design space for scalable many-core operating systems is yet to be fully explored.
Pseudo-Uniform Memory Architectures hide the memory's throughput bottlenecks and the network's latency differences in order to provide near-peak average throughput for computations on large datasets. This obviates the need for application-level partitioning and load balancing between NUMA domains but the performance of cross-core communication still depends on the actual placement of the involved variables and cores, which can result in significant variation within applications and between application runs.
This paper analyses the pseudo-uniform memory latency on the Intel Xeon Phi Knights Corner processor, derives strategies for the optimised placement of important variables, and discusses the role of localised coordination in pUMA systems. For example, a basic cache line ping-pong benchmark showed a 3x speedup between adjacent cores. Therefore, pUMA systems combined with support for controlled placement of small datasets are an interesting option when processor-wide load balancing is difficult while localised coordination is feasible.
The tiny logic elements in modern integrated circuits increase the rate of transient failures significantly. Therefore, redundancy on various levels is necessary to retain reliability. However, for mixed-criticality scenarios, the typical processor designs offer either too little fault-tolerance or too much redundancy for one part of the applications. Amongst others, we specifically address redundant processor internal functional units (FU) to cope with transient errors and support wear leveling. A real-time operating system (RTOS) was extended to control our prototypical hardware platform and, since it can be configured deterministically within few clock cycles, we are able to reconfigure the FUs dynamically, at process switching time, according to the specified critically of the running processes. Our mechanisms were integrated into the Plasma processor and the Plasma-RTOS. With few changes to the original software code, it was, for example, possible to quickly change from fault-detecting to fault-correcting modes of the processor on demand.