Parallel Processing Letters

This paper presents a new approach to resource management and scheduling in computational grids, in order to simplify the vision users have from grid resources and their management. Scheduling decisions are moved to the site where resources are hosted, allowing quick response to changes in load and resource availability. Users do not need to be aware of the resources they use and are instead supplied with "virtual resources" representing the amount of computational power available to them in the site. This approach results in new challenges, like the management of two-level scheduling schema and the need to define a site capacity measure, but simplifies and optimizes scheduling in grids. In this paper we present details of this approach – called Site Resource Scheduler (SRS) – as well as some issues regarding its simulated performance and its deployment in a site. We show that the main advantage of this approach is an overall reduction in the execution time of tasks in most scenarios.

In this short note, we use a generating function to give an explicit formula for the surface area of the star graphs.

Increasingly, real-time systems are being used in applications that contain tasks that have deadlines and require predictable performance. Many complex real-time applications require modern operating systems capable of scheduling multiple classes of tasks in an integrated way. These applications require scheduling that result in high utilization of available processing power to accommodate as many tasks as possible while satisfying the required deadlines of each task. In this paper, we propose a combined heuristic approach to schedule a set of independent soft and hard real-time tasks in multiprocessor computing systems. Each of these tasks is characterized by its arrival time, deadline and required processing power. The proposed approach distributes the total available processing power of any processor, if it is needed and possible, among more than one task, while ensuring that hard real-time tasks are given higher priority and enough processing power to meet deadlines. This strategy can be used as a tool to efficiently guide scheduling processes. In addition, it can help to optimize processor utilization and maintain higher success ratios by maximizing the schedulability of soft tasks without jeopardizing the schedulability of hard tasks.

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.

Unstructured peer-to-peer (P2P) networks suffer from the increased volume of traffic produced by flooding. Methods such as random walks or dynamic querying managed to limit the traffic at the cost of reduced network coverage. In this paper, we propose a partitioning method of the unstructured overlay network into a relative small number of distinct subnetworks. The partitioning is driven by the categorization of keywords based on a uniform hash function. The method proposed in this paper is easy to implement and results in significant benefit for the blind flood method. Each search is restricted to a certain partition of the initial overlay network and as a result it is much more targeted. Last but not least, the search accuracy is not sacrificed to the least since all related content is searched. The benefit of the proposed method is demonstrated with extensive simulation results, which show that the overhead for the implementation and maintenance of this system is minimal compared to the resulted benefit in traffic reduction.

The ability to obtain complex global behaviour from simple local rules makes cellular automata an interesting platform for massively parallel computation. However, manually designing a cellular automaton to perform a given computation can be extremely difficult, and automated design techniques such as genetic programming have their limitations because of the absence of human intuition. In this paper, we propose elements of a framework whose goal is to make the manual synthesis of cellular automata rules exhibiting desired global characteristics more programmer-friendly, while maintaining the simplicity of local processing elements. Although many of the framework elements that we describe here are not new, we group them into a consistent framework and show that they can all be implemented on a traditional cellular automaton, which means that they are merely more human-friendly ways of describing simple cellular automata rules, and not foreign structures that require changing the traditional cellular automaton model.

We characterize collective communication operations on (clustered) multiprocessor systems in terms of their communication volume, and arrive at useful relationships between regular and irregular operations over sets of processors and sets of cluster-nodes, respectively. We show that regular problems over sets of processors induce corresponding irregular problems over sets of nodes. We hereby identify a symmetric variant of the personalized all-to-all communication problem that might be worth studying in its own right, and discuss an algorithm for solving this problem. From a simple algorithm for the regular all-gather problem over sets of processors, we derive an algorithm for the irregular all-gather problem over both sets of processors and sets of nodes. For communication libraries like MPI, the relationships emphasize the need for efficient algorithms for the irregular collective communication operations.

Sorting networks are cost-effective multistage interconnection networks with sorting capabilities. These networks theoretically consume Θ(NlogN) comparisons. However, the fastest implementable sorting networks built so far consume Θ(Nlog²N) comparisons, and generally, use the Merge-sorting strategy to sort the input. An 18-element network using the Merge-sorting strategy needs at least 12 steps — here we show a network that sorts 18 elements in only 11 steps.

Plasmodium of Physarum polycephalum spans sources of nutrients and constructs varieties of protoplasmic networks during its foraging behavior. When the plasmodium is placed on a substrate populated with sources of nutrients, it spans the sources with protoplasmic network. The plasmodium optimizes the network to deliver efficiently the nutrients to all parts of its body. How exactly does the protoplasmic network unfold during the plasmodium's foraging behavior? What types of proximity graphs are approximated by the network? Does the plasmodium construct a minimal spanning tree first and then add additional protoplasmic veins to increase reliability and through-capacity of the network? We analyze a possibility that the plasmodium constructs a series of proximity graphs: nearest-neighbour graph (NNG), minimum spanning tree (MST), relative neighborhood graph (RNG), Gabriel graph (GG) and Delaunay triangulation (DT). The graphs can be arranged in the inclusion hierarchy (Toussaint hierarchy): NNG⊆MST⊆RNG⊆GG⊆DT. We aim to verify if graphs, where nodes are sources of nutrients and edges are protoplasmic tubes, appear in the development of the plasmodium in the order NNG→MST→RNG→GG→DT, corresponding to inclusion of the proximity graphs.

We consider the multimessage multicasting over the n processor complete (or fully connected) static network when there are l incoming (message) buffers on every processor. We present an efficient algorithm to route the messages for every degree d problem instance in d²/l + l - 1 total communication rounds, where d is the maximum number of messages that each processor may send (or receive). Our algorithm takes linear time with respect to the input length, i.e. O(n + q) where q is the total number of messages that all processors must receive. For l = d we present a lower bound for the total communication time. The lower bound matches the upper bound for the schedules generated by our algorithm. For convenience we assume that the network is completely connected. However, it is important to note that each communication round can be automatically translated into one communication round for processors interconnected via a replication network followed by a permutation network (e.g., two adjacent Benes networks), because in these networks all possible one-to-many communications can be performed in a single communication round.

We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of minimizing their latency. However, in doing so, they face the challenge of lack of precise information on the capacity of the network links. This uncertainty is modeled via a set of probability distributions over all the possibilities, one for each user. The resulting model is an amalgamation of the KP-model of [14] and the congestion games with user-specific functions of [22]. We embark on a study of Nash equilibria and the price of anarchy in this new model. In particular, we propose polynomial-time algorithms (w.r.t. our model's parameters) for computing some special cases of pure Nash equilibria and we show that negative results of [22], for the non-existence of pure Nash equilibria in the case of three users, do not apply to our model. Consequently, we propose an interesting open problem, that of the existence of pure Nash equilibria in the general case of our model. Furthermore, we consider appropriate notions for the social cost and the price of anarchy and obtain upper bounds for the latter. With respect to fully mixed Nash equilibria, we show that when they exist, they are unique. Finally, we prove that the fully mixed Nash equilibrium is the worst equilibrium.

Multi-core technology is a natural next step in delivering the benefits of Moore's law to computing platforms. On multi-core processors, the performance of many applications would be improved by parallel processing threads of codes using multi-threading techniques. This paper evaluates the performance of the multi-core Intel Xeon processors on the widely used basic linear algebra subprograms (BLAS). On two dual-core Intel Xeon processors with Hyper-Threading technology, our results show that a performance of around 20 GFLOPS is achieved on Level-3 (matrix-matrix operations) BLAS using multi-threading, SIMD, matrix blocking, and loop unrolling techniques. However, on a small size of Level-2 (matrix-vector operations) and Level-1 (vector operations) BLAS, the use of multi-threading technique speeds down the execution because of the thread creation overheads. Thus the use of Intel SIMD instruction set is the way to improve the performance of single-threaded Level-2 (6 GFLOPS) and Level-1 BLAS (3 GFLOPS). When the problem size becomes large (cannot fit in L2 cache), the performance of the four Xeon cores is less than 2 and 1 GFLOPS on Level-2 and Level-1 BLAS, respectively, even though eight threads are executed in parallel on eight logical processors.

In this paper, we investigate the scatter problem, which is defined as follows: Given a set of n robots, regardless of the initial position of the robots on the plane, eventually, no two robots are located at the same position forever. We show that this problem cannot be deterministically solved. Next, we propose a randomized algorithm. The proposed solution is trivially self-stabilizing. We then show how to design a self-stabilizing version of any deterministic solution for the Pattern Formation and the Gathering problems for any number n ≥ 2 of robots.