The OpenMP programming model provides a number of loop scheduling policies which the application developer can utilize to split loop iterations among the threads executing a parallel region. Because determining the optimal schedule policy and its parameters may be a tedious task, OpenMP offers a special schedule, called runtime; this allows the application developer to experiment with different scheduling policies at execution time, using a special environment variable, without the need to re-compile their program. However, there is a fundamental limitation to this facility: all application loops with the runtime schedule must follow the exact same scheduling policy. We propose a simple but effective extension that alleviates this limitation by allowing for different, per-loop runtime schedules. In addition, we use this mechanism to introduce extra loop scheduling policies which are not officially supported by OpenMP but may however prove effective in certain applications.

The recent OpenMP device constructs enable application writers to utilize the host CPUs along with other attached computational resources, in an intuitive and productive manner. These target-related directives offload portions of the program code (kernels) to any of the available computational devices; the kernels themselves can take advantage of the multiplicity of processing elements within the target device by employing OpenMP constructs. However, most co-processors or accelerators, especially embedded ones, have limited resources. This severely constrains the extend of OpenMP support that can be implemented within a device. A usual design decision is to support OpenMP partially, in effect hindering the full exploitation of the device capabilities through a high-level programming model. In this work, we present a novel solution to this problem for embedded multicores. We propose a compiler-assisted, adaptive runtime system organization, which generates application-specific support by implementing only the OpenMP functionality required each time. Full OpenMP support is available if needed. However, in the usual scenario where kernels do not require complex OpenMP functionalities, our method can lead to dramatically reduced executable sizes. Our proposal is demonstrated by a complete implementation on the popular Parallella board.

Reproducing complex networks with features of real-life networks is exciting and challenging at the same time. Based on the popular Omnet++ discrete event simulator, we introduce Armonia, a framework for modeling massive networks and their dynamic interactions. It includes a collection of topology generators, a set of resource placement and replication modules, a component for specifying resource location strategies, while also offering support for exporting data in order to visualize or analyze with other appropriate tools. Our framework targets search protocols in large-scale dynamic networks. Here, we apply it to simulate various probabilistic flooding strategies, making a comparative study of their performance over different network topologies.

With the increasing diversity of computing systems and the rapid performance improvement of commodity hardware, heterogeneous clusters become the dominant platform for low-cost, high-performance computing. Grid-enabled and heterogeneous implementations of MPI establish it as the de facto programming model for these environments. On the other hand, task parallelism provides a natural way for exploiting their hierarchical architecture. This hierarchy has been further extended with the advent of general-purpose GPU devices. In this paper we present the implementation of an MPI-based task library for heterogeneous and GPU clusters. The library offers an intuitive programming interface for multilevel task parallelism with transparent data management and load balancing. We discuss design and implementation issues regarding heterogeneity support and report performance results on heterogeneous cluster computing environments.

Abstract We present the development of a novel high‐performance face detection system using a neural network‐based classification algorithm and an efficient parallelization with OpenMP. We discuss the design of the system in detail along with experimental assessment. Our parallelization strategy starts with one level of threads and moves to the exploitation of nested parallel regions in order to further improve, by up to 19%, the image‐processing capability. The presented system is able to process images in real time (38 images/sec) by sustaining almost linear speedups on a system with a quad‐core processor and a particular OpenMP runtime library. Copyright © 2009 John Wiley & Sons, Ltd.

In this work we present the runtime architecture of the OMPi OpenMP compiler. OMPi is a source-to-source C translator featuring a portable, modular and extensible runtime system. It allows for OpenMP threads to map to different execution entities which range from kernel/user-level threads to processes, providing transparent support of OpenMP applications on both SMP machines and clusters of SMPs. When operating within an SMP machine, arbitrary threading libraries can be employed; currently a multitude of such libraries is available, including one which is based on portable user-level threading, for high-performance nested parallelism support. When operating on a cluster, processes are used as the execution entities and different software DSM cores can be utilized under a unified interface; the runtime system uses a hybrid approach whereby its internal bookkeeping is done through explicit message passing, while user-program shared variables are handled by the DSM core.

We consider flooding-based resource discovery in distributed systems. With flooding, a node searching for a resource contacts its neighbors in the network, which in turn contact their own neighbors and so on until a node possessing the requested resource is located. Flooding assumes no knowledge about the network topology or the resource distribution thus offering an attractive means for resource discovery in dynamically evolving networks such as peer-to-peer systems. We provide analytical results for the performance of a number of flooding-based approaches that differ in the set of neighbors contacted at each step. The performance metrics we are interested in are the probability of locating a resource and the average number of steps and messages for doing so. We study both uniformly random resource requests and requests in the presence of popular (hot) resources. Our analysis is also extended to take into account the fact that nodes may become unavailable either due to failures or voluntary departures from the system. Our analytical results are validated through simulation

In open multi-agent systems, agents need resources provided by other agents but they are not aware of which agents provide particular resources. We consider a peer-to-peer approach, in which each agent maintains a local cache with information about k resources, that is for each of the k resources, an agent that provides it. However, when an agent or a resource moves, cache entries become obsolete. We propose a suite of cache update policies that combine pull-based invalidation that is initiated by the agent that maintains the cache with push-based invalidation that is initiated by the agent that moves. We study and compare variations of oblivious flooding-based push/pull along with an informed push approach where each agent maintains a list of the agents that have it cached. Our experimental results indicate that a novel variation of flooding for push where a moving agent propagates its new location to agents in its old neighborhood achieves good cache consistency with a small message overhead. The proposed policies are suitable for any peer-to-peer system where peers cache information about other peers and this information becomes obsolete.

Consider an interconnection network and the following situation: Every node needs to send a different message to every other node. This is the total exchange or all-to-all personalized communication problem, one of a number of information dissemination problems known as collective communications. Under the assumption that a node can send and receive only one message at each step (single-port model), it is seen that the minimum time required to solve the problem is governed by the status (or total distance) of the nodes in the network. We present a time-optimal solution for any Cayley network. Rings, hypercubes, cube-connected cycles, and butterflies are some well-known Cayley networks which can take advantage of our method. The solution is based on a class of algorithms which we call node-invariant algorithms and which behave uniformly across the network.

Total exchange (or multiscattering) is one of the important collective communication problems in multiprocessor interconnection networks. It involves the dissemination of distinct messages from every node to every other node. We present a novel theory for solving the problem in any multidimensional (cartesian product) network. These networks have been adopted as cost-effective interconnection structures for distributed-memory multiprocessors. We construct a general algorithm for single-port networks and provide conditions under which it behaves optimally. It is seen that many of the popular topologies, including hypercubes, k-ary n-cubes, and general tori satisfy these conditions. The algorithm is also extended to homogeneous networks with 2/sup k/ dimensions and with multiport capabilities. Optimality conditions are also given for this model. In the course of our analysis, we also derive a formula for the average distance of nodes in multidimensional networks; it can be used to obtain almost closed-form results for many interesting networks.

Paschalis et al. (1988) have given a structured method to design TSC m-out-of-2m code checkers suitable for VLSI implementation. In this correspondence we give sufficient conditions so that the method previously given can be used to design checkers for classes of m-out-of-n codes with n/spl ne/2m.>

Allocating nodes in a concurrent computer system depends on the topology of the system. In this work, we present a number of processor allocation strategies for Hypercycle based concurrent systems. Hypercycles is a class of multidimensional interconnection networks which includes such widely used networks as the binary n-cubes, k-ary n-cubes, generalized hypercubes etc. The allocation strategies presented include a statically optimal first-fit allocation, a suboptimal-first fit, and strategies with extended search space through the inclusion of additional search lists formed by permuting the base through which a hypercycle is defined. For all these strategies, we examine their optimality and present simulation results characterizing their performance relative to each other.>