Summary Achieving efficient many‐to‐many communication on a given network topology is a challenging task when many data streams from different sources have to be scattered concurrently to many destinations with low variance in arrival times. In such scenarios, it is critical to saturate but not to congest the bisectional bandwidth of the network topology in order to achieve a good aggregate throughput. When there are many concurrent point‐to‐point connections, the communication pattern needs to be dynamically scheduled in a fine‐grained manner to avoid network congestion (links, switches), overload in the node's incoming links, and receive buffer overflow. Motivated by the use case of the Compressed Baryonic Matter experiment (CBM), we study the performance and variance of such communication patterns on a Cray XC40 with different routing schemes and scheduling approaches. We present a distributed Data Flow Scheduler (DFS) that reduces the variance of arrival times from all sources at least 30 times and increases the achieved aggregate bandwidth by up to 50%.

A pattern database (PDB) is a pre-computed lookup table storing shortest distances from abstract states to abstract goal states. PDBs are key components in heuristic search as their entries are used to prune paths that cannot lead to an optimal solution. With the sliding-tile puzzle as an exemplary application domain, we present methods to improve the precision and size of PDBs by improving additive pattern databases to zero-aware additive pattern databases (ZPDBs), reducing the compression rate from previously 1.6 bit to 1 bit per entry, generating optimal additive pattern partitionings, and building effective collections of pattern databases. With these enhancements, we achieve an overall 8.59-fold performance gain on the 24-puzzle compared to the previously best set of 6-tile PDBs.

Abstracts of the invited talks presented at SoCS 2014.

Key-based routing schemes, where a message is forwarded towards a server responsible for a partition in a large name space, does not provide strong delivery guarantees when the network is reconfigured with servers joining and leaving. This best-effort behavior is sufficient for eventually consistent data services such as key-value stores, content distribution networks or publish/subscribe systems. However, such schemes are not able to provide stronger consistency guarantees as required by, for example, metadata services and databases. We present RECODE, a framework for reconfigurable, consistent and decentralized data services. RECODE simplifies the implementation of strongly consistent data services, and continues to provide strong guarantees even during reconfiguration. More specifically, we introduce the routecast primitive which delivers messages for a key in the same total order, independent of the servers responsible for the key.We demonstrate the expressiveness and practical usability of RECODE by presenting three applications: a map of atomic registers, a set of distributed counters, and a lease management system. We evaluate the performance and elasticity of RECODE executing in a cluster.

SUMMARY MR‐Search is a framework for massively parallel heuristic search. Based on the MapReduce paradigm, it efficiently utilizes all available resources: processors, memories, and disks. MR‐Search uses OpenMP on shared memory systems, Message Passing Interface on clusters with distributed memory, and a combination of both on clusters with multi‐core processors. Large graphs that do not fit into the main memory can be efficiently processed with an out‐of‐core variant. We implemented two node expansion strategies in MR‐Search: breadth‐first frontier search and breadth‐first iterative deepening A*. With breadth‐first frontier search, we computed large and powerful table‐driven heuristics, so‐called pattern databases that exceed the main memory capacity. These pattern databases were then used to solve random instances of the 24‐puzzle with breadth‐first iterative deepening A* on systems with up to 4093 processor cores. MR‐Search is conceptually simple. It takes care of data partitioning, process scheduling, out‐of‐core data merging, communication, and synchronization. Application developers benefit from the parallel computational capacity without having the burden of implementing parallel application code. Copyright © 2011 John Wiley & Sons, Ltd.

Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.

Pattern databases (PDBs) store heuristic estimates that are used to improve the performance of heuristic search algorithms. They are key to the success of heuristic search in many application domains. While it is known [12] that the effectiveness of PDBs critically depends on their size, current implementations use only small PDBs because they require random access to main memory.

We present a distributed algorithm for identifying the location of data centers and their relative sizes. This topology information can be used in P2P systems to improve the routing performance, replica placement, or job scheduling. The algorithm uses gossiping with local agglomerative clustering. It is robust to failures and it correctly identifies outliers that are caused, e.g., by temporarily overloaded nodes or network failures. We present empirical results on the Grid 5000 testbed.

Structured Overlay Networks (SONs) provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. SONs provide lookup services that map keys to nodes that can be used as processing or storage resources. In SONs, lookups for a key may return inconsistent results. Consequently, it is difficult to provide consistent data services on top of SONs that build on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the affect of lookup inconsistencies can be reduced by using node responsibilities. We present our results as a trade-off between consistency and availability of keys.

Abstract We present a scheme for reserving job resources with imprecise requests. Typical parameters such as the estimated runtime, the start time or the type or number of required CPUs need not be fixed at submission time but can be kept fuzzy in some aspects. Users may specify a list of preferences which guide the system in determining the best matching resources for the given job. Originally, the impetus for our work came from the need for efficient co‐reservation mechanisms in the Grid where rigid constraints on multiple job components often make it difficult to find a feasible solution. Our method for handling fuzzy reservation requests gives the users more freedom to specify the requirements and it gives the Grid Reservation Service more flexibility to find optimal solutions. In the future, we will extend our methods to process co‐reservations. We evaluated our algorithms with real workload traces from a large supercomputer site. The results indicate that our scheme greatly improves the flexibility of the solution process without having much affect on the overall workload of a site. From a user's perspective, only about 10% of the non‐reservation jobs have a longer response time, and from a site administrator's view, the makespan of the original workload is extended by only 8% in the worst case. Copyright © 2006 John Wiley & Sons, Ltd.

We present an architectural framework for specifying and processing co-reservations in grid environments. Compared to other approaches, our co-reservation framework is more general. It can be applied to the reservation of applications running concurrently on multiple resources (multi-site applications) and to the planning of job flows, where the components may be linked by some temporal or spatial relationship. We introduce the concept of virtual resources that allows to compose resources by abstracting from their specific features. Among other features, virtual resources enable advanced co-reservation with nested resource levels, resource aggregation, and transparent fault recovery.

Core Grid technologies are rapidly maturing, but there remains a shortage of real Grid applications. One important reason is the lack of a simple and high-level application programming toolkit, bridging the gap between existing Grid middleware and application-level needs. The Grid Application Toolkit (GAT), as currently developed by the EC-funded project GridLab, provides this missing functionality. As seen from the application, the GAT provides a unified simple programming interface to the Grid infrastructure, tailored to the needs of Grid application programmers and users. A uniform programming interface will be needed for application developers to create a new generation of "Grid-aware" applications. The GAT implementation handles both the complexity and the variety of existing Grid middleware services via so-called adaptors. Complementing existing Grid middleware, GridLab also provides high-level services to implement the GAT functionality. We present the GridLab software architecture, consisting of the GAT, environment-specific adaptors, and GridLab services. We elaborate the concepts underlying the GAT and outline the corresponding application programming interface. We present the functionality of GridLab's high-level services and demonstrate how a dynamic Grid application can easily benefit from the GAT. All GridLab software is open source and can be downloaded from the project Web site.

Clusters provide an outstanding cost/performance ratio, but their efficient orchestration, i.e. their cooperative management, maintenance, and use, still poses difficulties. Moreover, many sites operate multiple clusters, each possible running under a different cluster management system. In this paper, we present an architectural scheme for the coordinated management of multiple clusters in a fabric. Our scheme allows different cluster management systems to interact with each other via adaptors, thereby providing interoperability within a single administrative entity, the fabric. Using adaptors, various jobs (grid jobs, local jobs, system maintenance jobs) can be served by the same methods, and existing cluster management software (like LSF, PBS, CCS, etc.) can be extended by additional functions without much modification effort.

The Testbed and Applications working group of the European Grid Forum (EGrid) is actively building and experimenting with a grid infrastructure connecting several research-based supercomputing sites located in Europe. The paper reports on our first feasibility study: running a self-migrating version of the Cactus simulation code across the European grid testbed, including "live" remote data visualization and steering from different demonstration booths at Supercomputing 2000, in Dallas, TX. We report on the problems that had to be resolved for this endeavour and identify open research challenges for building production-grade grid environments.

RSD (Resource and Service Description) is a software architecture for specifying, registering and accessing resources and services in complex heterogeneous computing environments. It has three major components: a graphical resource editor, a compiler system for translating textual specifications, and an application programming interface. In this paper we focus on the language definition and the compiler system that generates portable data objects for registering and accessing distributed resources. We also present the mechanism used by RSD to maintain information on the status of dynamic resources such as CPU load or network bandwidth. RSD is a purely descriptive tool that provides up-to-date information on system resources. Other tools, like resource brokers, mappers or job migrators, build on it.

We present a software system for the management of geographically distributed high-performance computers. It consists of three components: 1. The Computing Center Software (CCS) is a vendor-independent resource management software for local HPC systems. It controls the mapping and scheduling of interactive and batch jobs on massively parallel systems; 2. The Resource and Service Description (RSD) is used by CCS for specifying and mapping hardware and software components of (meta-)computing environments. It has a graphical user interface, a textual representation and an object-oriented API; 3. The Service Coordination Layer (SCL) co-ordinates the co-operative use of resources in autonomous computing sites. It negotiates between the applications' requirements and the available system services. Copyright © 1999 John Wiley & Sons, Ltd.

Iterative-deepening searches mimic a breadth-first node expansion with a series of depth-first searches that operate with successively extended search horizons. They have been proposed as a simple way to reduce the space complexity of best-first searches like A* from exponential to linear in the search depth. But there is more to iterative-deepening than just a reduction of storage space. As the authors show, the search efficiency can be greatly improved by exploiting previously gained node information. The information management techniques considered here owe much to their counterparts from the domain of two-player games, namely the use of fast-execution memory functions to guide the search. The authors' methods not only save node expansions, but are also faster and easier to implement than previous proposals.>