Catálogo de publicaciones - libros

In recent years, the world has seen a tremendous increase in the capability to create, share and store multimedia items, i.e. a combination of pictorial, linguistic, and auditory data. Moreover, in emerging multimedia applications, generation, processing, storage, indexing, querying, retrieval, delivery, shielding, and visualization of multimedia content are integrated issues, all taking place at the same time and - potentially - at different administrative domains. As a result of these trends, a number of novel and hard research questions arise, which can be answered only by applying techniques of parallel, distributed, and Grid computing.

Supporting Video-on-Demand (VoD) services in Internet is still a challenging issue due to high bandwidth requirement of multimedia contents and additional constraints imposed by such environment: higher delays and jitter, network congestion, non-symmetrical clients’ bandwidth and inadequate support for multicast communications. This paper presents DynaPeer, a peer-topeer VoD delivery policy designed for Internet environment. Our design defines a Virtual Server, which is responsible for establishing a group of peers, enabling service for new client requests by aggregating the necessary clients’ resources. Virtual Server operates in both unicast and multicast environments, thereby improving system performance. To demonstrate the effectiveness of DynaPeer, we have developed an analytical model to evaluate its performance, understood as the server-load reduction due to request service distributed among peers. We conducted a performance comparison study of our proposal with classic unicast, multicast (Patching) and other P2P delivery schemes, such as Pn2Pm, Chaining and Promise, improving their performance by 45%, 59%, 74% respectively, even when taking into account Internet constraints.

Due to the increasing performance requirements of decoding H.264/AVC in HDTV or larger resolutions, new approaches are necessary to enable real-time processing. According to the current trend to parallel computation in all performance classes, decoding of AVC must be mapped to these architectures even though this is complicated by the increased complexity and many data dependencies in the codec. We propose and evaluate different ways of using multithreading to speed-up our .NET implemented decoder. While slice based approaches scale best, this is not a flexible approach because of the reliance on specially encoded streams. Functional partitioning and macroblock pipelining prove to be a good alternative for almost all evaluated videos.

Theory of parallel computation is still a widely unanswered field of research. The lack of truly parallel data structures (such as quantum computing may provide one day) still prevents us from obtaining a unified framework for the design of parallel algorithms, and the design of parallel algorithms remains a case-by-case challenge. As the complexity-related questions have been progressively (and regrettably) abandoned, theoretical research in parallel computing focuses today on two main areas: the classical design of parallel algorithms for specific problems; and very recently, modeling, understanding and formalizing how entities/structures/networks interact in parallel in order to design better parallel algorithms.

This work introduces a set of important improvements in the resolution of the Two Dimensional Cutting Stock Problem. It presents a new heuristic enhancing existing ones, an original upper bound that lowers the upper bounds in the literature, and a parallel algorithm for distributed memory machines that achieves linear speedup. Many components of the algorithm are generic and can be ported to parallel branch and bound and A* skeletons. Among the new components there is a comprehensive -compatible synchronization service which facilitates the writing of time-based balancing schemes.

We investigate the following very simple load-balancing algorithm on the -cycle ( even) which we call (OETB). The edges of the cycle are partitioned into two matchings canonically. A matching defines a single step, the two matchings form a single round. Processors connected by an edge of the matching perfectly balance their loads, and, if there is an excess token, it is sent to the lower-numbered processor. The difference between the real process where the tokens are assumed integral and the idealized process where the tokens are assumed divisible can be expressed in terms of the local divergence [1]. We show that Odd-Even Transposition Balancing has a local divergence of /2 − 1. Combining this with previous results, this shows that after (log()) rounds, any input sequence with initial imbalance is perfectly balanced. Experiments are presented that show that the number of rounds necessary to perfectly balance a load sequence with imbalance that has been obtained by pre-balancing a random sequence with much larger imbalance is significally larger than the average number of rounds necessary for balancing random sequences with imbalance .

We present in detail a GCA (Global Cellular Automaton) algorithm with 3 cells for Hirschberg’s algorithm which determines the connected components of a -node undirected graph with time complexity (log). This algorithm is implemented fully parallel in hardware (FPGA logic). The complexity of the logic and the performance is evaluated and compared to a former implementation using ( + 1) cells with a time complexity of ( log( )). It can be seen from the implementation that the presented algorithm needs significantly fewer resources (logic elements times computation time) compared to the implementation with ( + 1) cells, making it preferable for graphs of reasonable size.

In this work we study preference systems suitable for the Peer-to-Peer paradigm. Most of them fall in one of the three following categories: global, symmetric and complementary. All these systems share an acyclicity property. As a consequence, they admit a stable (or Pareto efficient) configuration, where no participant can collaborate with better partners than their current ones.

We analyze the representation of such preference systems and show that any acyclic system can be represented with a symmetric mark matrix. This gives a method to merge acyclic preference systems while retaining the acyclicity property. We also consider properties of the corresponding collaboration graph, such as clustering coefficient and diameter. In particular, the study of the example of preferences based on real latency measurements shows that its stable configuration is a small-world graph.

Communication networks are likely among the most crucial resources for parallel and distributed computer systems. The last couple of years has seen many significant technical improvements, ranging from advanced on-chip interconnects, via system and storage-area networks, up to dedicated, optical wide-area networks. While this technology push is bringing new opportunities, it also comes with many new research challenges.

Both QoS support and congestion management techniques have become essential for achieving good performance in current high-speed interconnection networks. However, traditional techniques proposed for both issues require too many resources for being implemented. In this paper we propose a new switch architecture that efficiently uses the same resources to offer both congestion management and QoS provision. It is as effective as previous proposals, but much more cost-effective.