### Simulating Grid Schedulers with Deadlines and Co-Allocation.

• By: Alexis Ballier , Eddy Caron , Dick Epema , Hashim Mohamed
• Number: RR2006-01
• Date: January 2006
• Abstract:

One of the true challenges in resource management in grids is to provide support for co-allocation, that is, the allocation of resources in multiples autonomous subsystems of a grid to single jobs. With reservation-based local schedulers, a grid scheduler can reserve processors with these schedulers to achieve simultaneous processor availability. However, with queuing-based local schedulers, it is much more difficult to guarantee this. In this paper we present mechanisms and policies for working around the lack of reservation mechanisms for jobs with deadlines that require co-allocation, and simulations of these mechanisms and policies.
• Keywords:

Grid, Scheduling, Simulation.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+10p
• Format: Portable Document Format
• Get it
• Revisions: none

### Parameterized floating-point logarithm and exponential functions for FPGAs.

• By: Jérémie Detrey, Florent de Dinechin
• Number: RR2006-02
• Date: January 2006
• Abstract:

As FPGAs are increasingly being used for floating-point computing, the feasibility of a library of floating-point elementary functions for FPGAs is discussed. An initial implementation of such a library contains parameterized operators for the logarithm and exponential functions. In single precision, those operators use a small fraction of the FPGA's resources, have a smaller latency than their software equivalent on a high-end processor, and provide about ten times the throughput in pipelined version. Previous work had shown that FPGAs could use massive parallelism to balance the poor performance of their basic floating-point operators compared to the equivalent in processors. As this work shows, when evaluating an elementary function, the flexibility of FPGAs provides much better performance than the processor without even resorting to parallelism. The presented library is freely available from {\url{http://www.ens-lyon.fr/LIP/Arenaire/}.
• Keywords:

Elementary functions, parameterized operators, logarithm, exponential, floating-point, FPGA, FPLibrary.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+13p
• Format: Compressed postscript
• Get it
• Revisions: none

### A fully distributed scheme to turn a network into a small world.

• By: Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel
• Number: RR2006-03
• Date: January 2006
• Abstract:

We investigate the problem of efficiently preprocessing a large network, in a fully distributed manner, so that the resulting network is a navigable small world. Namely, if the network has bounded growth, by adding a single entry in a distributed manner to each routing table (using $O(n)$ rounds and $O(\operatorname{polylog} n)$ space), we obtain a network in which the greedy routing algorithm computes paths of polylogarithmic expected length between any pair of nodes. A bounded growth graph is a graph of constant expansion rate, \emph{i.e.} the number of nodes within distance $2r$ from a given node is at most a constant times the number of nodes within distance $r$. These graphs are considered as a relevant framework for real networks as Peer-to-peer networks where our scheme could be used to considerably improve the routing speed over time. We also extends our algorithm to graphs of polylogarithmic expansion rate. Recent small world models provide augmentation processes of large graph classes into navigable small worlds via the addition of new random links to each node. However, the computation of the required random links distribution kept these processes unrealistic for large decentralized networks. Our algorithm, based on a careful sampling of a set of leader nodes, bypasses these limitations.
• Keywords:

Distributed algorithms, navigable small world, routing algorithms, bounded growth.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+13p
• Format: Compressed postscript
• Get it
• Revisions: none

### Interaction efficace entre les réseaux rapides et le stockage distribué dans les grappes de calcul.

• By: Brice Goglin, Olivier Glück, and Pascale Vicat-Blanc Primet
• Number: RR2006-04
• Date: January 2006
• Abstract:

Les applications parallèles s'exécutant sur les grappes nécessitent à la fois des communications performantes entre les différents noeuds et des accès efficaces au système de stockage. Nous proposons dans ce travail d'améliorer les performances du stockage distribué dans les grappes en utilisant au mieux le réseau haute performance sous-jacent pour accéder au stockage distant. Nous montrons que les besoins du stockage sont très différents de ceux du calcul parallèle et proposons différentes solutions pour résoudre, au niveau du système de fichiers, les problèmes liés au contrôle du réseau mais montrons qu'il est nécessaire de modifier l'interface de programmation réseau et le système d'explotation pour venir à bout des difficultés liées au transfert de données. Des expérimentations montrent qu'elles permettent une utilisation aisée et efficace des réseaux rapides dans le cadre du stockage distribué.
• Keywords:

Stockage distribué, accès aux fichiers distants, grappe de calcul, réseau haute performance, zéro-copie, messages inattendus, notification d'événements.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+25p
• Format: Portable Document Format
• Get it
• Revisions: none

### Finding a Vector Orthogonal to Roughly Half a Collection of Vectors.

• By: Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé
• Number: RR2006-05
• Date: January 2006
• Abstract:

Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{2})^d$, there exists a vector in $E$ which is orthogonal to at least $N/3$ and at most $2N/3$ vectors of the family. We show that the range $[N/3,2N/3]$ can be replaced by the much smaller range $[N/2-\sqrt{N}/2,N/2+\sqrt{N}/2]$ and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.
• Keywords:

Algebraic complexity, decision trees, parallel algorithms, derandomization.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+11p
• Format: Compressed postscript
• Get it
• Revisions: none

### Scilab and MATLAB Interfaces to MUMPS (version 4.6 or greater).

• By: Aurélia Fèvre , Jean-Yves L'Excellent , Stéphane Pralet (ENSEEIHT-IRIT)
• Number: RR2006-06
• Date: January 2006
• Abstract:

This document describes the Scilab and MATLAB interfaces to MUMPS version 4.6. We describe the differences and similarities between usual Fortran/C MUMPS interfaces and its Scilab/MATLAB interfaces, the calling sequences and functionalities. Examples of use and experimental results are also provided.
• Keywords:

Direct solver, Sparse matrices, MUMPS, Scilab, MATLAB.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+22p
• Format: Portable Document Format
• Get it
• Revisions: none

### A library of Taylor models for PVS automatic proof checker.

• By: Francisco Cháves, Marc Daumas
• Number: RR2006-07
• Date: February 2006
• Abstract:

We present in this report a library to compute with Taylor models, a technique extending interval arithmetic to reduce decorrelation and to solve differential equations. Numerical software usually produces only numerical results. Our library can be used to produce both results and proofs. As seen during the development of Fermat's last theorem reported by Aczel 1996, providing a proof is not sufficient. Our library provides a proof that has been thoroughly scrutinized by a trustworthy and tireless assistant. PVS is an automatic proof assistant that has been fairly developed and used and that has no internal connection with interval arithmetic or Taylor models. We built our library so that PVS validates each result as it is produced. As producing and validating a proof, is and will certainly remain a bigger task than just producing a numerical result our library will never be a replacement to imperative implementations of Taylor models such as Cosy Infinity. Our library should mainly be used to validate small to medium size results that are involved in safety or life critical applications..
• Keywords:

PVS, program verification, interval arithmetic, Taylor models.
• Availability: Electronic copy only.
• Citation: Reliable Engineering Computing 2006.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Revisions: none

### Booting and Porting Linux and uClinux on a new platform.

• By: Nicolas Fournel, Antoine Fraboulet, Paul Feautrier
• Number: RR2006-08
• Date: February 2006
• Abstract:

T This research report presents a full case study on porting and booting the Linux and uCLinux operating system on a new platform. We present this work on the ARM Excalibur CM922TXA10 for which a new machine type has been created to be able to run the platform in a standalone mode.
• Keywords:

Linux, uCLinux, Operating System, ARM Platform, Porting.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+26p
• Format: Portable Document Format
• Get it
• Revisions: none

### A Doubling Dimension Threshold $\Theta(\log\log n)$ for Augmented Graph Navigability.

• By: Pierre Fraigniaud, Emmanuelle Lebhar and Zvi Lotker
• Number: RR2006-09
• Date: February 2006
• Abstract:

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining wether such an augmentation is possible for all graphs. In this paper, we answer negatively to this question by exhibiting a threshold on the doubling dimension, above which an infinite family of Cayley graphs cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\log\log n)$ are navigable. We show that for doubling dimension $\gg \log\log n$, an infinite family of Cayley graphs cannot be augmented to become navigable. Our proof relies on a result of independent interest: we show that the analysis of greedy routing worst performances on graphs augmented by arbitrary distributions of edges can be reduced to the analysis assuming a symmetric distribution. Finally, we complete our result by studying square meshes, that we prove to always be augmentable to become navigable.
• Keywords:

doubling dimension, small world, greedy routing, Cayley graphs.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+9p
• Format: Portable Document Format
• Get it

### Separating Real-Time and Linear Space Recognition of Languages on One-Dimensional Cellular Automata.

• By: Victor Poupet
• Number: RR2006-10
• Date: February 2006
• Abstract:

In this article we will focus on a famous open question about algorithmic complexity classes on one dimensional cellular automata, and we will show that if all problems recognizable in space n (where n is the length of the input) can be recognized in time n then for every space-constructible function f all the problems that are recognizable in space f can be recognized in time f.
• Keywords:

Cellular automata, language recognition, real-time, linear space.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+14p
• Format: Portable Document Format
• Get it
• Revisions: none

### VoroNet: A scalable object network based on Voronoi tessellations.

• By: Olivier Beaumont , Anne-Marie Kermarrec , Loris Marchal , Etienne Rivière
• Number: RR2006-11
• Date: February 2006
• Abstract:

In this paper, we propose the design of VoroNet, an object-based peer to peer overlay network relying on Voronoi tessellations, along with its theoretical analysis and experimental evaluation. VoroNet differs from previous overlay networks in that peers are application objects themselves and get identifiers reflecting the semantics of the application instead of relying on hashing functions. Thus it provides a scalable support for efficient search in large collections of data. In VoroNet, objects are organized in an attribute space according to a Voronoi diagram. VoroNet is inspired from the Kleinberg's small-world model where each peer gets connected to close neighbours and maintains an additional pointer to a long-range node. VoroNet improves upon the original proposal as it deals with general object topologies and therefore copes with skewed data distributions. We show that VoroNet can be built and maintained in a fully decentralized way. The theoretical analysis of the system proves that the routing in VoroNet can be achieved in a poly-logarithmic number of hops in the size of the system. The analysis is fully confirmed by our experimental evaluation by simulation.
• Keywords:

Overlay network, peer-to-peer, scalability, small-world networks, Voronoi tessellations, Computational geometry.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+21p
• Format: Portable Document Format
• Get it
• Revisions: none

### Porting the Mutek Operating System to ARM platforms.

• By: Nicolas Fournel, Antoine Fraboulet, Paul Feautrier
• Number: RR2006-12
• Date: March 2006
• Abstract:

This report presents the work done on modifying the lightweight Mutek operating system to add support for two complex Arm-based SoC architectures. Both of these platform use nearly the same ARMv4 core CPU model but have a different memory map and integrate different system peripherals such as interrupt controller, timer and serial interfaces. An initial support for MMU operations using an identity mapping has also been added to the hardware abstraction layer. This support was compulsory to access hardware information needed to activate the data cache.
• Keywords:

Mutek, Operating System, ARM-based Platform, Porting.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+32p
• Format: Portable Document Format
• Get it
• Revisions: none

### Register Allocation: What does Chaitin's NP-completeness Proof Really Prove?

• By: Florent Bouchez, Alain Darte, Fabrice Rastello
• Number: RR2006-13
• Date: March 2006
• Abstract:

Register allocation is one of the most studied problem in compilation. It is considered as an NP-complete problem since Chaitin, in 1981, showed that assigning temporary variables to k machine registers amounts to color, with k colors, the interference graph associated to variables and that this graph can be arbitrary, thereby proving the NP-completeness of the problem. However, this original proof does not really show where the complexity comes from. Recently, the re-discovery that interference graphs of SSA programs can be colored in polynomial time raised the question: Can we exploit SSA to perform register allocation in polynomial time, without contradicting Chaitin's NP-completeness result? To address such a question, we revisit Chaitin's proof to better identity the interactions between spilling (load/store insertion), coalescing/splitting (moves between registers), critical edges (a property of the control-flow graph), and coloring (assignment to registers). In particular, we show when it is easy to decide if temporary variables can be assigned to k registers or if some spilling is necessary. The real complexity comes from critical edges, spilling, and coalescing, which are addressed in our other reports.
• Keywords:

Register allocation, SSA form, chordal graph, NP-completeness, critical edge.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Revisions: none

### A Monitoring and Visualization Tool and Its Application for a Network Enabled Server Platform.

• By: Raphaël Bolze , Eddy Caron , Frédéric Desprez , Georg Hoesch , Cyril Pontvieux
• Number: RR2006-14
• Date: April 2006
• Abstract:

Monitoring grid platforms has recently gained a wide interest. This kind of platform highly distributed across different domains leads to several design and implementation problems. We have designed a new monitoring platform and visualization tool adapted for Network Enabled Server systems. This environment, highly tunable for different middleware platforms has been successfully validated on the DIET platform. In this paper, we present its architecture and main features as well as details of the validation on the DIET environment and experimental results on a large scale grid platform.
• Keywords:

Grid Computing, Monitoring, Visualization.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+11p
• Format: Portable Document Format
• Get it
• Revisions: none

### On the Complexity of Register Coalescing.

• By: Florent Bouchez, Alain Darte, Fabrice Rastello
• Number: RR2006-15
• Date: April 2006
• Abstract:

Due to the increasing latencies of memory accesses and recent developments on the SSA form, it has become important to revisit the spilling (load/store insertion) and register coalescing (removal of move instructions) problems in order to develop more aggressive register allocation strategies. This report is devoted to the complexity of register coalescing. We distinguish several optimizations that occur in most coalescing heuristics: a) aggressive coalescing removes as many moves as possible, regardless of the colorability of the resulting interference graph; b) conservative coalescing removes as many moves as possible while keeping the colorability of the graph; c) incremental conservative coalescing removes one particular move while keeping the colorability of the graph; d) optimistic coalescing coalesces all moves (when possible), aggressively, and gives up about as few moves as possible (de-coalescing) so that the graph becomes colorable. We (almost) completely classify the NP-completeness of these problems, discussing also on the structure of the interference graph (arbitrary, chordal, or k-colorable in a greedy fashion). We believe that such a study is a necessary step for designing new coalescing strategies.
• Keywords:

Register allocation, register coalescing, SSA form, chordal graph, NP-completeness, (greedy)-k-colorable graph.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+19p
• Format: Portable Document Format
• Get it
• Revisions: none

### A Doubling Dimension Threshold $\Theta(\log\log n)$ for Augmented Graph Navigability.

• By: Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker
• Number: RR2006-16
• Date: April 2006
• Abstract:

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining wether such an augmentation is possible for all graphs. In this paper, we answer negatively to this question by exhibiting a threshold on the doubling dimension, above which an infinite family of graphs cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\log\log n)$ are navigable. We show that for doubling dimension $\gg \log\log n$, an infinite family of graphs cannot be augmented to become navigable. Our proof relies on a result of independent interest: we show that the analysis of greedy routing worst performances on graphs augmented by arbitrary distributions of edges can be reduced to the analysis assuming a symmetric distribution. Finally, we complete our result by studying square meshes, that we prove to always be augmentable to become navigable.
• Keywords:

doubling dimension, small world, greedy routing.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+7p
• Format: Portable Document Format
• Get it

### GoDIET: a deployment tool for distributed middleware on \gk.

• By: Eddy Caron , Pushpinder Kaur Chouhan , Holly Dail
• Number: RR2006-17
• Date: April 2006
• Abstract:

In this article we present GoDIET, a tool for the configuration, launch, and management of the Distributed Interactive Engineering Toolbox (DIET) on computational grids. DIET is an Application Service Provider (ASP) platform providing remote execution of computational problems on distributed resources. GoDIET automatically generates and stages all necessary configuration files, launches agents and servers in appropriate hierarchical order, reports feedback on the status of running components, and allows shutdown of all launched software. GoDIET requires an XML file describing available compute and storage resources and the desired overlay of DIET agents and servers onto available resources. For homogeneous clusters, the XML file can be generated according to a deployment planning model, which has shown that an optimal DIET deployment on homogeneous clusters is a Complete Spanning $d$-ary (CSD) tree, where $d$ is the number of children directly attached to an agent, regardless of whether the children are servers or agents. We present experiments, that permit the evaluation of the performance of GoDIET for several launch and management approaches, that verify the correctness of the deployed platform, and that test the performance of CSD tree deployments optimized for uniform workloads under mixed workload scenarios.
• Keywords:

Deployment, ASP, Grid computing.
• Availability: Electronic copy only.
• Citation: ExpGrid 2006.
• Size: 2+14p
• Format: Portable Document Format
• Get it
• Revisions: none

### Grid flow control: Prototype of a grid gateway based on Network Processors.

• By: Sebastien Soudan , Pascale Primet
• Number: RR2006-18
• Date: May 2006
• Abstract:

Due to network bandwidth growth, grid computing has been envisionned. As grids are aggregation of computer clusters based on high performance local networks and interconnected by very high speed core networks, access links to core networks remain bottleneck locations. In order to optimize grid computing overall performance, we propose to organize data transfers from one cluster to an other. This organization must allow ressource schedulers to schedule data transferts in addition of tasks. Based on a grid network resource reservation model this paper presents the design f a grid gateway, located at the LAN/WAN interface. To implement this approach, we have develop a prototype based on Network Processors Intel IXP2400 which is able to control flows at 1 gigabits/s. We discuss the main design choices and experimental results.
• Keywords:

Network Processor, Grid, IXP2400, gateway.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+11p
• Format: Portable Document Format
• Get it
• Revisions: none

### Minimizing the stretch when scheduling flows of divisible requests.

• By: Arnaud Legrand , Alan Su , Frédéric Vivien
• Number: RR2006-19
• Date: October 2006
• Abstract:

In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive uni-processor case, and we show how to extend algorithms that have been proposed in the literature for the uni-processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any on-line algorithm, we present new competitiveness results for existing algorithms, and we develop several new on-line heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics in realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the uni-processor model prove to be inefficient in practice. In contrast, we show our on-line algorithms based on linear programming to be near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case.
• Keywords:

Bioinformatics, heterogeneous computing, scheduling, divisible load, linear programming, stretch.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 3+68p
• Format: Portable Document Format
• Get it

### A flexible bandwidth reservation framework for bulk data transfers in grid networks.

• By: Bin Bin Chen , Pascale Primet
• Number: RR2006-20
• Date: June 2006
• Abstract:

In grid networks, distributed resources are interconnected by wide area network to support compute and data-intensive applications, which require reliable and efficient transfer of gigabits (even terabits) of data. Different from best-effort traffic in Internet, bulk data transfer in grid requires bandwidth reservation as a fundamental service. Existing reservation schemes such as RSVP are designed for real-time traffic specified by reservation rate, transfer start time but with unknown lifetime. In comparison, bulk data transfer requests are defined in terms of volume and deadline, which provide more information, and allow more flexibility in reservation schemes, i.e., transfer start time can be flexibly chosen, and reservation for a single request can be divided into multiple intervals with different reservation rates. We define a flexible reservation framework using time-rate function algebra, and identify a series of practical reservation scheme families with increasing generality and potential performance, namely, FixTime-FixRate, FixTime-FlexRate, FlexTime-FlexRate, and Multi-Interval. Simple heuristics are used to select representative scheme from each family for performance comparison. Simulation results show that the increasing flexibility can potentially improve system performance, minimizing both blocking probability and mean flow time. We also discuss the distributed implementation of proposed framework.
• Keywords:

Reservation, grid, bulk data transfer, flexibility.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+19p
• Format: Portable Document Format
• Get it
• Revisions: none

### Valiant's model: from exponential sums to exponential products.

• By: Pascal Koiran, Sylvain Perifel
• Number: RR2006-21
• Date: June 2006
• Abstract:

We study the power of big products for computing multivariate polynomials in a Valiant-like framework. More precisely, we define a new class \vpip as the set of families of polynomials that are exponential products of easily computable polynomials. We investigate the consequences of the hypothesis that these big products are themselves easily computable. For instance, this hypothesis would imply that the nonuniform versions of P and NP coincide. Our main result relates this hypothesis to Blum, Shub and Smale's algebraic version of P versus NP. Let $K$ be a field of characteristic 0. Roughly speaking, we show that in order to separate $\p_K$ from $\np_K$ using a problem from a fairly large class of simple'' problems, one should first be able to show that exponential products are not easily computable. The class of simple'' problems under consideration is the class of NP problems in the structure $(K,+,-,=)$, in which multiplication is not allowed.
• Keywords:

Algebraic complexity, Valiant's model, Blum-Shub-Smale's model, big products.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Get it (web archive)
• Revisions: none

### Multi-phase On-chip Traffic Generation Environment.

• By: Antoine Scherrer, Antoine Fraboulet, Tanguy Risset
• Number: RR2006-22
• Date: June 2006
• Abstract:

In this report, we present a cycle-accurate multi-phase on-chip traffic generation and simulation environment. This environment provides deterministic traffic generation (traces replay) as well as stochastic traffic generation based on statistical analysis of a reference trace. We show that our traffic generators emulate precisely the behavior of the processors and that our environment is a versatile tool for network-on-chip prototyping. Simulations are performed in a SystemC-based simulation environment with a mesh network-on-chip.
• Keywords:

on-chip traffic, multi-phase, stochastic analysis.
• Availability: Electronic copy only.
• Citation: Proceedings of "Application-specific Systems, Architectures and Processors (ASAP 06)", Steamboat Springs, USA, September 11-13, 2006.
• Size: 2+15p
• Format: Portable Document Format
• Get it
• Revisions: none

### Scheduling and data redistribution strategies on star platforms.

• By: Loris Marchal, Veronika Rehn, Yves Robert, Frédéric Vivien
• Number: RR2006-23
• Date: June 2006
• Abstract:

In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.
• Keywords:

Master-slave platform, scheduling, data redistribution, one-port model, independent tasks, divisible load theory.
• Availability: Electronic copy only.
• Citation: Master-slave platform, scheduling, data redistribution, one-port model, independent tasks, divisible load theory.
• Size: 2+37p
• Format: Portable Document Format
• Get it
• Revisions: none

### XCP-i : eXplicit Control Protocol for heterogeneous inter-networking of high-speed networks.

• By: D. M. Lopez-Pacheco , Congduc Pham (LIUPPA, University of Pau, France) , Laurent Lefèvre
• Number: RR2006-24
• Date: June 2006
• Abstract:

XCP is a transport protocol that uses the assistance of specialized routers to accurately determine the sender's congestion window size. However, XCP requires the collaboration of all the routers on the data path which is almost impossible to achieve in an incremental deployment scenario of XCP. It has been shown that XCP behaves worse than TCP in the presence of non-XCP routers, limiting dramatically the benefit of having XCP running in some parts of the network. In this paper, we address this problem and propose XCP-i which is operable on an internetwork consisting of XCP routers and traditional IP routers without loosing the benefit of the XCP control laws. The simulation results on a number of topologies that reflect the various scenario of incremental deployment on the Internet show that although XCP-i performances depend on available bandwidth estimation accuracy, XCP-i still outperforms TCP on high-speed links.
• Keywords:

TCP, XCP, non-XCP router, non-XCP cloud, XCP virtual router.
• Availability: Electronic copy only.
• Citation: TCP, XCP, non-XCP router, non-XCP cloud, XCP virtual router.
• Size: 2+14p
• Format: Compressed postscript
• Get it
• Revisions: none

### Scheduling communication requests traversing a switch: complexity and algorithms.

• By: Matthieu Gallet, Yves Robert, Frédéric Vivien
• Number: RR2006-25
• Date: June 2006
• Abstract:

In this paper, we study the problem of scheduling file transfers through a switch. This problem is at the heart of a model often used for large grid computations, where the switch represents the core of the network interconnecting the various clusters that compose the grid. We establish several complexity results, and we introduce and analyze various algorithms, from both a theoretical and a practical perspective.
• Keywords:

Grid computing, networks, scheduling file transfers, switch, complexity.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+28p
• Format: Portable Document Format
• Get it
• Revisions: none

### MPICH/Madeleine : Evaluation et optimisation des performances longue distance.

• By: Ludovic Hablot, Olivier Glück
• Number: RR2006-26
• Get it (Web Archive)

### On the Probabilistic Query Complexity of Transitively Symmetric Problems.

• By: Pascal Koiran, Vincent Nesme et Natacha Portier
• Number: RR2006-27
• Date: June 2006
• Abstract:

We obtain optimal lower bounds on the nonadaptive probabilistic query complexity of a class of problems defined by a rather weak symmetry condition. In fact, for each problem in this class, given a number T of queries we compute exactly the performance (i.e., the probability of success on the worst instance) of the best nonadaptive probabilistic algorithm that makes T queries. We show that this optimal performance is given by a minimax formula involving certain probability distributions. Moreover, we identify two classes of problems for which adaptivity does not help. We illustrate these results on a few natural examples, including unordered search, Simon's problem, distinguishing one-to-one functions from two-to-one functions, and hidden translation. For these last three examples (which are of particular interest in quantum computing), the recent theorems of Aaronson, of Laplante and Magniez, and of Bar-Yossef, Kumar and Sivakumar on the probabilistic complexity of black-box problems do not yield any nonconstant lower bound.
• Keywords:

probabilistic query complexity, lower bounds, symmetry.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+18p
• Format: Compressed postscript
• Get it

### LSP Matrix Decomposition Revisited.

• By: Claude-Pierre Jeannerod
• Number: RR2006-28
• Date: September 2006
• Abstract:

In this paper, we study the problem of computing an LSP-decomposition of a matrix over a field. This decomposition is an extension to arbitrary matrices of the well-known LUP-decomposition of full row-rank matrices. We present three different ways of computing an LSP-decomposition, that are both rank-sensitive and based on matrix multiplication. In all cases, for an $m$ by $n$ input matrix of unknown rank $r$, the costs we obtain are $O(mnr^{\omega-2})$ for $\omega > 2$. When $r$ is small, this improves the $O(nm^{\omega-1})$ complexity bound of Ibarra, Moran and Hui.
• Keywords:

Matrix factorization, matrix multiplication, reduced echelon form, rank profile, algorithmic complexity.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+14p
• Format: Portable Document Format
• Get it
• Revisions: none

### VPSPACE and a transfer theorem over the reals.

• By: Pascal Koiran, Sylvain Perifel
• Number: RR2006-29
• Get it (Web Archive)

### Strategies for Replica Placement in Tree Networks.

• By: Anne Benoit , Veronika Rehn , Yves Robert
• Number: RR2006-30
• Date: October 2006
• Abstract:

In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program..
• Keywords:

Replica placement, tree networks, access policy, scheduling, complexity results, heuristics, heterogeneous clusters.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+34p
• Format: Portable Document Format
• Get it
• Revisions: none

### DIET: New Developments and Recent Results.

• By: A. Amar, R. Bolze, A. Bouteiller, A. Chis, Y. Caniou, E. Caron, P.K. Chouhan, G. Le Mahec, H. Dail, B. Depardon, F. Desprez, J.-S. Gay, A. Su
• Number: RR2006-31
• Date: October 2006
• Abstract:

Among existing grid middleware approaches, one simple, powerful, and flexible approach consists of using servers available in different administrative domains through the classic client-server or Remote Procedure Call (RPC) paradigm. Network Enabled Servers (NES) implement this model also called GridRPC. Clients submit computation requests to a scheduler whose goal is to find a server available on the grid. The aim of this paper is to give an overview of an NES middleware developed in the GRAAL team called \diet and to describe recent developments. \diet (Distributed Interactive Engineering Toolbox) is a hierarchical set of components used for the development of applications based on computational servers on the grid.
• Keywords:

Grid Computing, Network Enabled Servers, Client-Server Computing.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+17p
• Format: Portable Document Format
• Get it
• Revisions: none

### Simbatch: an API for simulating and predicting the performance of parallel resources and batch systems.

• By: Jean-Sébastien Gay, Yves Caniou
• Number: RR2006-32
• Date: October 2006
• Abstract:

The study of scheduling algorithms for parallel tasks in a grid computing context either neglects local reservation systems which manage parallel resources, either suppose that they use a First Come First Served strategy, or the experimental model does not handle parallel tasks. In this report, we describe an API built in the grid simulation tool Simgrid. It offers core functionalities to simulate in a realistic way parallel resources and batch reservation systems. Simbatch simulation experiments show an error rate inferior to 1% compared to real life experiments conducted with the OAR batch manager.
• Keywords:

Scheduling, Grid simulation, Batch systems, Performance prediction.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+13p
• Format: Portable Document Format
• Get it
• Revisions: none

### A Dynamic Prefix Tree for Service Discovery within Large Scale Grids.

• By: Eddy Caron , Frédéric Desprez , Cédric Tedeschi
• Number: RR2006-33
• Date: October 2006
• Abstract:

Within computational grids, some services (software components, linear algebra libraries, etc.) are made available by some servers to some clients. In spite of the growing popularity of such grids, the service discovery, although efficient in many cases, does not reach several requirements. Among them, the flexibility of the discovery and its efficiency on wide-area dynamic platforms are two major issues. Therefore, it becomes crucial to propose new tools coping with such platforms. Emerging peer-to-peer technologies provide algorithms allowing the distribution and the retrieval of data items while addressing the dynamicity of the underlying network. We study in this paper the service discovery in a pure peer-to-peer environment. We describe a new trie-based approach for the service discovery that supports range queries and automatic completion of partial search strings, while providing fault-tolerance, and partially taking into account the topology of the underlying network. We validate this approach both by analysis and simulation. Traditional metrics considered in peer-to-peer systems exhibits interesting complexities within our architecture. The analysis' results are confirmed by some simulation experiments run using several grid's data sets.
• Keywords:

Service discovery, computational grids, peer-to-peer, prefix trees.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+14p
• Format: Portable Document Format
• Get it
• Revisions: none

### A Repair Mechanism for Fault-Tolerance for Tree-Structured Peer-to-Peer Systems.

• By: Eddy Caron , Frédéric Desprez , Charles Fourdrignier , Franck Petit, Cédric Tedeschi
• Number: RR2006-34
• Date: October 2006
• Abstract:

Facing the limits of traditional tools of resource management within computational grids (related to scale, dynamicity, etc. of the platforms newly considered), new approaches, based on peer-to-peer technologies are emerging. The resource discovery and in particular the service discovery is concerned by this evolution. Among the solutions, a promising one is the indexing of resources using trie structures and more particularly prefix trees. The major advantages of trie-structured approaches is the capability to support search queries on ranges of values with a latency growing logarithmically in the number of nodes in the trie. Those techniques are easy to extend to multicriteria searches. One drawback of using tries is its inherent poor robustness in a dynamic environment, where nodes join and leave the network, leading to the split of the tree into a forest, which results in the impossibility to route requests. Within most recent approaches, the fault-tolerance is a prevention mechanism, often replication-based. The replication can be costly in term of resources required. In this paper, we propose a fault-tolerance protocol that reconnects subtrees a posteriori, after crashes, to have again a connected graph and then reorder the nodes to rebuild a consistent tree.
• Keywords:

Fault tolerance, peer-to-peer, prefix trees.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Revisions: none

### Systèmes de types purs explicites, réduction du sujet et préservation de la normalisation forte.

• By: Romain Kervarc
• Number: RR2006-35
• Date: October 2006
• Abstract:

Pure type systems are an elegant formalism allowing to specify in a very easy way a large number of type systems. The possibility of their extension to calculi with explicit substitution was the object of numerous studies, which ran into various problems. In particular, the intuitive systems obtained by the mere addition of a cut rule to type substitutions have a major flaw: they do not satisfy subject reduction. In this report, we introduce pure type systems based upon the explicit substitution calculus with names lambda x, and we show that our systems satisfy among others subject reduction, and that they preserve the strong normalisation of their implicit counterparts.
• Keywords:

lambda-calculus, explicit substitution, intuitionnistic logic, pure type systems, higher order types, calculus of constructions, lambda-cube, subject reduction, strong normalisation.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+69p
• Format: Compressed postscript
• Get it

### Systèmes de types purs et séquents classique.

• By: Romain Kervarc
• Number: RR2006-36
• Date: October 2006
• Abstract:

The bar lambda mu tilde mu-calculus was designed by P.-L. Curien and H. Herbelin. One of its interest is that its terms can be interpreted as derivations in the classical sequent calculus. One of the its lacks is the fact that it has only simple types. Our purpose here is to extend the calculus to higher-order types, and especially those of the calculus of constructions, a calculus designed by T. Coquand and G. Huet in order to provide a very general typed language for proof assistants based on \lambda-calculus. In order to do this, we place ourselves in the framework of pure type systems, which are a very general formalism allowing to represent many interesting type systems, among which those of Barendregt's lambda-cube, which is a hierarchical presentation of the calculus of constructions. We show that our systems satisfy some fundamental properties, such as subject reduction, and strong normalisation on the lambda-cube.
• Keywords:

lambda-calculus, bar lambda mu tilde mu-calculus, classical logic, sequent calculus, pure type systems, higher order types, calculus of constructions, lambda-cube, subject reduction, strong normalisation.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+9p
• Format: Compressed postscript
• Get it
• Revisions: none

### Embedded systems energy characterization methodology using non-intrusive instrumentation.

• By: Nicolas Fournel, Antoine Fraboulet, Paul Feautrier
• Number: RR2006-37
• Date: November 2006
• Abstract:

This research report presents a non intrusive methodology for building embedded systems energy consumption models. The method is based on measurement on real hardware in order to get a quantitative approach that takes into account the full architecture. Based on these measurements, data are grouped into class of instructions and events. These classes can then be reused in software simulators and in high-level source code transformation cost functions for optimizing compilers. The computed power model is much more simpler than previous power models while being accurate at the platform level. The methodology is illustrated using experimental results made on an ARM Integrator platform for which an accurate and full system energy model is build.
• Keywords:

Embedded Systems, Energy Consumption Model, Simulation Instrumentation, Optimizing Compilers Cost Functions.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+32p
• Format: Portable Document Format
• Get it
• Revisions: none

### Investigation of Ethernet switches behavior in presence of contending flows at very high-speed.

• By: Sebastien Soudan, Romaric Guillier, Ludovic Hablot, Yuetsu Kodama, Tomohiro Kudoh, Fumihiro Okazaki, Pascale Primet, Ryousei Takano
• Number: RR2006-38
• Date: November 2006
• Abstract:

.
• Keywords:

.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+21p
• Format: Portable Document Format
• Get it
• Get it (Web Archive)
• Revisions: none

### Revisiting Matrix Product on Master-Worker Platforms.

• By: Jack Dongarra, Jean-François Pineau, Yves Robert, Zhiao Shi, Frédéric Vivien
• Number: RR2006-39
• Date: November 2006
• Abstract:

This paper is aimed at designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative:
- Centralized data. We assume that all matrix files originate from, and must be returned to, the master. The master distributes both data and computations to the workers (while in ScaLAPACK, input and output matrices are initially distributed among participating resources). Typically, our approach is useful in the context of speeding up MATLAB or SCILAB clients running on a server (which acts as the master and initial repository of files)..
- Heterogeneous star-shaped platforms. We target fully heterogeneous platforms, where computational resources have different computing powers. Also, the workers are connected to the master by links of different capacities. This framework is realistic when deploying the application from the server, which is responsible for enrolling authorized resources.
- Limited memory. Because we investigate the parallelization of large problems, we cannot assume that full matrix panels can be stored in the worker memories and re-used for subsequent updates (as in ScaLAPACK). The amount of memory available in each worker is expressed as a given number of buffers, where a buffer can store a square block of matrix elements. The size q of these square blocks is chosen so as to harness the power of Level 3 BLAS routines: q=80 or 100 on most platforms.

We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of numerical experiments on various platforms at École Normale Supérieure de Lyon and the University of Tennessee. However, we point out that in this first version of the report, experiments are limited to homogeneous platforms
• Keywords:

Matrix product, LU decomposition, Master-worker platform, Heterogeneous platforms, Scheduling.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+26p
• Format: Portable Document Format
• Get it
• Revisions: none

### Mapping pipeline skeletons onto heterogeneous platforms.

• By: Anne Benoit, Yves Robert
• Number: RR2006-40
• Date: November 2006
• Abstract:

Mapping applications onto parallel platforms is a challenging problem, that becomes even more difficult when platforms are heterogeneous --nowadays a standard assumption. A high-level approach to parallel programming not only eases the application developer's task, but it also provides additional information which can help realize an efficient mapping of the application. In this paper, we discuss the mapping of pipeline skeletons onto different types of platforms: fully homogeneous platforms with identical processors and interconnection links; communication homogeneous platforms, with identical links but different speed processors; and finally, heterogeneous platforms. We assume that a pipeline stage must be mapped on a single processor, and we establish new theoretical complexity results for two different mapping policies: a mapping can be either one-to-one (a processor is assigned at most one stage), or interval-based (a processor is assigned an interval of consecutive stages). We provide several efficient polynomial heuristics for the most important policy/platform combination, namely interval-based mappings on communication homogeneous platforms.
• Keywords:

Algorithmic skeletons, pipeline, scheduling, complexity results, heuristics, heterogeneous clusters.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+23p
• Format: Portable Document Format
• Get it
• Get it (web archive)

### Plug-in Scheduler Design for a Distributed Grid Environment.

• By: Eddy Caron , Andréea Chis , Frédéric Desprez , Alan Su
• Number: RR2006-41
• Date: November 2006
• Abstract:

This report presents the approach chosen within the DIET (Distributed Interactive Engineering Toolbox) project a Grid-RPC environment to allow a resource broker to be tuned for specific application classes. Our design allows the use of generic or application dependent performance measures in a simple and seamless way.
• Keywords:

Grid Computing, Scheduling, Performance Prediction.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+10p
• Format: Portable Document Format
• Get it
• Revisions: none

### Evaluation des performances de TCP sur le réseau de Grid'5000.

• By: Romaric Guillier, Ludovic Hablot, Pascale Primet, Sébastien Soudan
• Number: RR2006-42
• Date: November 2006
• Abstract:

L'instrument Grid'5000 est destiné à l'étude des problématiques, des solutions et des logiciels de grille pour le calcul et le stockage distribué à large échelle. En 2006, Grid'5000 s'est doté d'un réseau privé virtuel composé de liens d'accès à 1 ou 10Gb/s et de longueurs d'onde à 10Gb/s dédiées dans l'infrastructure DWDM de RENATER 4. Ce rapport présente une étude de l'apport potentiel de cette infrastructure pour les applications distribuées via une évaluation des performances de TCP, protocole prépondérant dans ces applications. Cette étude met d'abord en lumière l'incidence très importante du paramétrage du protocole dans un tel contexte et explique le faible débit observé tant par l'opérateur que par les utilisateurs. Les résultats obtenus via un calibrage adéquat ou l'utilisation de flux parallèles sont ensuite présentés. Enfin, plusieurs anomalies de configuration et de comportement de l'infrastructure sont exposées.
• Keywords:

TCP, 10 GbE, Grid'5000, paramètrage de TCP.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Get it (Web Archive)
• Revisions: none

### A study of large flow interactions in high-speed shared networks with Grid5000 and GtrcNET-10 instruments.

• By: Romaric Guillier, Ludovic Hablot, Yuetsu Kodama, Tomohiro Kudoh, Fumihiro Okazaki, Pascale Primet, Sébastien Soudan et Ryousei Takano
• Number: RR2006-43
• Abstract:

We consider the problem of huge data transfers and bandwidth sharing in contexts where transfer delay bounds are required. This report investigates large flow interactions in a real very high-speed network and aims at contributing to high-speed TCP variants evaluation by providing precise measurements. It then also gives an insight on the behaviour of emulated alternative protocols under different realistic congestion and long latency conditions in 10~Gbps experimental environments.
• Keywords:

bulk data transfers, bandwidth sharing, transfer delay predictability, transport protocol experimentation.
• Availability: Electronic copy only.
• Citation: PFLDnet2007.
• Size: 2+9p
• Format: Portable Document Format
• Get it
• Get it (Web Archive)
• Revisions: none

### Découverte de services pour les grilles de calcul dynamiques large échelle.

• By: Cédric Tedeschi
• Number: RR2006-44
• Date: November 2006
• Abstract:

Dans les grilles des serveurs offrent des services aux clients afin de réaliser des calculs. Avant de pouvoir les utiliser, les clients doivent être à même de les retrouver. Bien que les différentes solutions proposées depuis l'émergence des grilles soient efficaces sur des plates-formes relativement statiques et de petite échelle, elles ne sont plus en adéquation avec la nature dynamique et à large échelle des grilles futures. Pour de tels environnements de nouveaux outils doivent être proposés, notamment des mécanismes pour la découverte de services, qui devront être \emphflexibles et passer à l'échelle dans des environnements dynamiques. Nous étudions dans ce papier la découverte de services pour des grilles de calcul pair-à-pair. Nous proposons une nouvelle architecture basée sur un arbre de plus long préfixes.
• Keywords:

Découverte de services, grilles de calcul, pair-à-pair, arbres de préfixes.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+11p
• Format: Portable Document Format
• Get it
• Revisions: none

### Return of the hardware floating-point elementary function.

• By: Jérémie Detrey, Florent de Dinechin, Xavier Pujol
• Number: RR2006-45
• Get it (Web Archive)

### Exact and mid-point rounding cases of power(x,y).

• By: Lauter, Christoph Quirin
• Number: RR2006-46
• Get it (Web Archive)

### Towards a Transparent Data Access Model for the GridRPC Paradigm.

• By: Gabriel Antoniu , Eddy Caron , Frédéric Desprez , Mathieu Jan
• Number: RR2006-47
• Date: December 2006
• Abstract:

As grids become more and more attractive for solving complex problems with high computational and storage requirements, the need for adequate grid programming models is considerable. To this purpose, the GridRPC model has been proposed as a grid version of the classical RPC paradigm, with the goal to build NES (Network-Enabled Server) environments. Paradoxically enough, in this model, data management has not been defined and is now explicitly left at the user's charge. The contribution of this paper is to enhance data management in NES by introducing a transparent data access model, available through the concept of grid data-sharing service. Data management (persistent storage, transfer, consistent replication) is totally delegated to the service, whereas the applications simply access shared data via global identifiers. We illustrate our approach using the DIET GridRPC middleware and the JuxMEM data-sharing service. Experiments performed on the Grid'5000 testbed demonstrate the benefits of the proposed approach.
• Keywords:

GridRPC, Data Sharing, Persistency, JuxMEM, DIET.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+12p
• Format: Portable Document Format
• Get it
• Revisions: none

### Impact of QoS on Replica Placement in Tree Networks.

• By: Anne Benoit , Veronika Rehn , Yves Robert
• Number: RR2006-48
• Date: December 2006
• Abstract:

This paper discusses and compares several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. We study three strategies. The first two strategies assign each client to a unique server while the third allows requests of a client to be processed by multiple servers. The main contribution of this paper is to assess the impact of QoS constraints on the total replication cost. In this paper, we establish the NP-completeness of the problem on homogeneous networks when the requests of a given client can be processed by multiple servers. We provide several efficient polynomial heuristic algorithms for NP-complete instances of the problem. These heuristics are compared to the optimal solution provided by the formulation of the problem in terms of the solution of an integer linear program.
• Keywords:

Replica placement, tree networks, access policy, scheduling, complexity results, heuristics, heterogeneous clusters, quality of service.
• Availability: Electronic copy only.
• Citation: Not published yet.
• Size: 2+23p
• Format: Portable Document Format
• Get it
• Revisions: none

### A certified infinite norm for the validation of numerical algorithms.

• By: Sylvain Chevillard and Christoph Lauter
• Number: RR2006-49
• Get it (Web Archive)