Catálogo de publicaciones - libros

Peer-to-peer distributed storage systems usually replicate data objects on multi-node to improve the performance and availability. However, updates may be delayed for P2P systems are generally large-scale and strong distributed, and then the performance of resource location in Internet would be depressed. According to that, an optimistic data consistency maintenance method based on key-attributes is proposed. In the method, updates about key-attributes are separated from user request. Key-updates are propagated by latency-overlay update propagation model, that is, updates are always propagated to nodes having maximum or minimal latency, and assured and uncertain propagation paths of updates are all taken into account. Based on classifying key-update conflicts, a double-level reconciling mechanism including the preprocessing of buffer and the processing of update-log is applied to detect and reconcile conflicts, and then conflicts are solved by policies of last-writer-win and divide-and-rule. Lastly, the technique of managing and maintaining update-log is discussed for the above is deployed based on the information storied in update-log. Delaying key-attributes updates cannot occur by the optimistic disposal method, and then it cannot depress efficiency of resource location based on key-attributes, which adapts well to P2P systems in Internet. The simulation results show it is an effective optimistic consistency maintenance method, achieves good consistency overhead, resource location and access overhead, and has strong robustness.

The Cell processor is a typical example of a heterogeneous multiprocessor-on-chip architecture that uses several levels of parallelism to deliver high performance. Closing the gap between peak performance and sustained performance is the challenge for software tool developers and the application developers. Image processing and media applications are typical ”main stream” applications. In this paper, we use the Harris algorithm for detection of points of interest (PoI) in an image as a benchmark to compare the performance of several parallel schemes on a Cell processor. The impact of the DMA controlled data transfers and the synchronizations between SPEs explains the differences between the performance of the different parallelization schemes. These results will be used to design a tool for an efficient mapping of image processing applications on multi-core architectures.

We have proposed and evaluated a novel heuristic algorithm of routing and wavelength assignment (RWA) for scheduled lightpath demands (SLD). Our algorithm is shown here to have a performance gain in terms of the number of wavelengths up to 65.8% compared with the most recently introduced method, TDP_RWA, and works on directed and undirected optical networks. Also, we show the execution time of our proposed method is feasible.

This work evaluates two artificial intelligence techniques for file distribution in Grid environments. These techniques are used to access data on independent servers in parallel, in order to improve the performance and maximize the throughput rate. In this work, genetic algorithms and Hopfield neural networks are the techniques used to solve the problem. Both techniques are evaluated for efficiency and performance. Experiments were conduced in environments composed of 32, 256 and 1024 distributed nodes. The results allow to confirm the decreasing in the file access time and that Hopfield neural network offered the best performance, being possible to be applied on Grid environments.

Graph problems are finding increasing applications in high performance computing disciplines. Although many regular problems can be solved efficiently in parallel, obtaining efficient implementations for irregular graph problems remains a challenge. We propose techniques for designing and implementing efficient parallel algorithms for graph problems on symmetric multiprocessors and chip multiprocessors with a case study of parallel tree and connectivity algorithms. The problems we study represent a wide range of irregular problems that have fast theoretic parallel algorithms but no known efficient parallel implementations that achieve speedup without serious restricting assumptions about the inputs. We believe our techniques will be of practical impact in solving large-scale graph problems.

We present the first investigation of the well-known memorization technique for solving the problem in a distributed setting. Memorization was introduced by Robson [15] in his paper on solving the problem. The idea is to augment a recursive algorithm with the capability to store subproblem instances and solutions of bounded size in a table that can be quickly referenced, so that subproblems are guaranteed to be solved exactly once. This approach has recently been applied with success to improve the complexity of the fixed-parameter tractable algorithms for solving the problem [12,5]. We present a general parallel approach for using memorization to solve the problem where the subgraphs are precomputed [12]. In this case, the subgraphs and corresponding solutions are generated in a preprocessing step, rather than during the recursion. Our technique makes efficient use of the processors generating the lookup table, while at the same time requiring less space. We describe a distributed algorithm using this technique, well-suited to cluster or grid computing platforms.

The present work describes the design of a distributed agent system devoted to the Dial-a-Ride Problem. This routing and scheduling problem consists in finding a set of routes and schedules for each vehicle that satisfies a set of trip requests comming from users. The agent system distributes an improved insertion heuristic for the scheduling of passengers’ trip requests over a fleet of vehicles. Agents make use of the contract-net protocol as base coordination mechanism for the planning and scheduling of passenger trips.

A coloring of a graph  = (,) is a partition of {, ⋯ } of into independent sets called color classes. A vertex  ∈  is called a Grundy vertex if it is adjacent to at least one vertex in color class , for every  < . In the partial Grundy coloring, every color class contains at least one Grundy vertex. Such a coloring gives a partitioning of the graph into clusters for which every cluster has a clusterhead (the Grundy vertex) adjacent to some other clusters. Such a decomposition is very interesting for large distributed systems and networks. In this paper, we propose a distributed algorithm to maintain the partial Grundy coloring of any graph G when an edge is added

Traditional parallel schedulers running on cluster supercomputers support only static scheduling, where the number of processors allocated to an application remains fixed throughout the execution of the job. This results in under-utilization of idle system resources thereby decreasing overall system throughput. In our research, we have developed a prototype framework called ReSHAPE, which supports dynamic resizing of parallel MPI applications executing on distributed memory platforms. The resizing library in ReSHAPE includes support for releasing and acquiring processors and efficiently redistributing application state to a new set of processors. In this paper, we derive an algorithm for redistributing two-dimensional block-cyclic arrays from to processors, organized as 2-D processor grids. The algorithm ensures a contention-free communication schedule for data redistribution if  ≤  and  ≤ . In other cases, the algorithm implements circular row and column shifts on the communication schedule to minimize node contention.

The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity test of graphs in a distributed environment based on a constructive approach. The contribution of this paper is threefold. First, using a pre-constructed spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local knowledge. Second, we present an encoding of this protocol using graph relabeling systems. The last contribution is the implementation of this protocol in the message passing model. For a given graph where is the number of its edges, the number of its nodes and is its degree, our algorithms need the following requirements: The first one uses steps and bits per node. The second one uses messages and time and bits per node. Furthermore, the studied network is : Only the root of the pre-constructed spanning tree needs to be identified. Moreover, we investigate some applications that can use our protocol as a pre-processing task for initial configurations.