Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Marc Daumas Janvier, Sylvie Boldo, ...
A simple test qualifying the accuracy of Horner's rule for polynomials
Unit Mixte, Cormac Walsh, Bruno Gaujal, ...
A linear algorithm for real-time scheduling with optimal energy use
Dynamics of the Picking transformation on integer partitions (2007)
Unit Mixte, Phan Ti, Ha Duong, ...
This paper studies a conservative transformation dened on families of nite sets. It consists in removing one element from each set and adding a new set composed of the removed elements. This...
Unit Mixte, Erich Kaltofen, Gilles Villard Janvier
Computing the sign or the value of the determinant of an integer matrix, a complexity survey
Unit Mixte, Bernd Beckermann, Bernd Beckermann, ...
We present an algorithm for the computation of a shifted Popov Normal Form of a rectangular polynomial matrix. For specic input shifts, we obtain methods for computing the matrix greatest common...
Matrix Rank Certication (2007)
Unit Mixte, B. David Saunders, B. David Saunders, ...
Randomized algorithms are given for computing the rank of a matrix over a eld of characteristic zero. The matrix is treated as a black box. Only the capability to compute matrix column-vector and...
An Application-Level Network Mapper (2007)
Unit Mixte, Arnaud Legrand, Arnaud Legr, ...
This paper presents a tool to automatically discover the network topology. The goal is to evaluate the performance of concurrent transfers (for example to improve collective communications) and not...
Heterogeneous Multi-Cluster Networking with the Madeleine III Communication Library (2007)
Unit Mixte, Olivier Aumage Fvrier, Olivier Aumage
This paper introduces the new version of the Madeleine portable multi-protocol communication library. Madeleine version III now includes full, exible multicluster support associated to a redesigned...
Laboratoire de l'Informatique du Parall lisme (2007)
Unit Mixte, Cyril Banino, Olivier Beaumont, Arnaud Legrand, ...
Scheduling strategies for master-slave tasking on heterogeneous processor grids
Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Olivier Beaumont, Olivier Beaumont, ...
A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs
Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Arnaud Legr, Helene Renard, ...
Load-balancing iterative computations in heterogeneous clusters with shared communication links Arnaud Legrand,
A Realistic Model and an Ecient Heuristic (2007)
Unit Mixte, Vincent Boudet, Olivier Beaumont, ...
Scheduling computational tasks on processors is a key issue for highperformance computing. Although a large number of scheduling heuristics have been presented in the literature, most of them target...
Unit Mixte, Gabriel Antoniu, Gabriel Antoniu, ...
DSM-PM2: A portable implementation platform for multithreaded DSM consistency protocols (extended version)
Remote object detection in cluster-based Java (2007)
Unit Mixte, Gabriel Antoniu, Gabriel Antoniu, ...
Our work combines Java compilation to native code with a run-time library that executes Java threads in a distributed-memory environment with true parallelism. To provide the illusion of a shared...
Ecient Matrix Preconditioners for (2007)
Unit Mixte, L. Chen, L. Chen, ...
The main idea of the black box approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the...
The Data Broadcast Problem with Preemption (2007)
Unit Mixte, Nicolas Schabanel Septembre, Nicolas Schabanel
The data-broadcast problem consists in nding an innite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the cost of the...
Shear-Warp Algorithm on a Cluster of PCs (2007)
Unit Mixte, Frdrique Chaussumier, Frdrique Chaussumier, ...
In the medical eld, volume rendering provides good quality 3D visualizations but it is still not interactive enough for a day-to-day practice. The most ecient sequential algorithm is the Shear-Warp...
Addressed Term Rewriting Systems (2007)
Unit Mixte, Frdric Lang, Frdric Lang, ...
We propose Addressed Term Rewriting Systems (ATRS) as a solution to the still-standing problem of nding a simple yet formally useful framework that can account for computation with sharing, cycles,...
Laboratoire de l'Informatique du Parall lisme (2007)
Unit Mixte, Nicolas Brisebarre, Nicolas Brisebarre, Georges Philibert, ...
Eective lower and upper bounds for the Fourier coecients of powers of the modular invariant j
Unit Mixte, Loris Marchal, Yves Robert, ...
Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms
Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Nicolas Brisebarre, Nicolas Brisebarre, ...
Finding the "truncated " polynomial that is closest to a function
Automatic Deployment for Hierarchical Network Enabled (2007)
Unit Mixte, Arnaud Legrand, Eddy Caron, ...
This paper focus on the deployment of grid infrastructures, more specifically Problem Solving Environments (PSE) for numerical applications on the grid. Even if the deployment of such an architecture...
Unit Mixte, Tom Hirschowitz, Tom Hirschowitz
Mixin modules are a notion of modules that allows cross-module recursion and late binding, two features missing in ML-style modules. They have been well dened in a call-by-name setting, but in a...
Algorithmic Issues on Heterogeneous Computing Platforms (2007)
Unit Mixte, Fr#d#ric Vivien, Pierre Boulet, ...
This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). Dealing with processors of dioeerent speeds...
Scheduling tasks sharing les from distributed repositories (2007)
Unit Mixte, Arnaud Giersch, Arnaud Giersch, ...
Scheduling tasks sharing les from distributed repositories
Unit Mixte, Helene Renard, Helene Renard, ...
Static load-balancing techniques for iterative computations on heterogeneous clusters
Unit Mixte, Alain Darte, Alain Darte, Robert Schreiber, ...
A constructive solution to the juggling problem in systolic array synthesis
Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Arnaud Giersch, Arnaud Giersch, ...
Scheduling tasks sharing les on heterogeneous clusters
Laboratoire de l'Informatique du Paralllisme (2007)
Unit Mixte, Arnaud Legr, Helene Renard, ...
Load-balancing iterative computations in heterogeneous clusters with shared communication links Arnaud Legrand,
Load-Balancing Scatter Operations for Grid Computing (2007)
Unit Mixte, Stphane Genaud, Stphane Genaud, ...
We present solutions to statically load-balance scatter operations in parallel codes run on grids. Our load-balancing strategy is based on the modication of the data distributions used in scatter...
Completing the Picture: Soundness of Formal Encryption in thePresence of Active Adversaries (2005)
Unit Mixte, Recherche Cnrs, Inpg Ujfcentre Equation, Active Adversaries, R. Janvier, Y. Lakhnech, ...
o 19
Computing Schedules for MultithreadedReal-Time Programs using Geometry (2004)
Unit Mixte, Recherche Cnrs, Inpg Ujfcentre Equation, Thao Dang, Thao Dangg
Reports are downloadable at the following
A symbolic decision procedure forcryptographic protocols with time (2004)
Unit Mixte, Recherche Cnrs, Inpg Ujfcentre Equation, Stamps L. Bozga, C. Ene, Y. Lakhnech, ...
Report no 02
Pattern-based Abstraction for Verifying Secrecy in Protocols2 (2004)
Unit Mixte, Recherche Cnrs, Inpg Ujfcentre Equation, L. Bozga, Y. Lakhnech, L. Bozga, ...
Abstract We present a method based on abstract interpretation for verifying secrecy properties of crypto-graphic protocols. Our method allows to verify secrecy properties in a general model allowing...
optimizing the steady-state throughput of Broadcasts on heterogeneous platforms (2003)
Unit Mixte, Arnaud Legrand, Arnaud Legr, ...
In this paper, we consider the communications involved by the execution of a complex application, deployed on a heterogeneous "grid" platform. Such applications extensively use...
Performance Analysis of Remote File System Access over High Bandwidth Local Network (2003)
Unit Mixte, Brice Goglin, Brice Goglin, ...
We study the performance of file servers, comparing NFS implementation in Linux to our experimental lightweight system called ORFA. The aim is to find out NFS bottlenecks in the case of high...
Steady-State Scheduling Of Task Graphs On Heterogeneous Computing Platforms (2003)
Unit Mixte, Arnaud Legrand, Olivier Beaumont, ...
In this paper, we consider the execution of a complex application on a heterogeneous "grid" computing platform. The complex application consists of a suite of identical, independent...
From Heterogeneous Task Scheduling to Heterogeneous Mixed Data and Task Parallel Scheduling (2003)
F. Suter, Unit Mixte, Frdric Suter, Henri Casanova, ...
Mixed-parallelism, the combination of data- and task-parallelism, is a powerful way of increasing the scalability of entire classes of parallel applications. Exploiting both types of parallelism...
Load-Balancing Scatter Operations for Grid Computing (2003)
Unit Mixte, Stéphane Genaud, Stphane Genaud, ...
We present solutions to statically load-balance scatter operations in parallel codes run on grids. Our load-balancing strategy is based on the modication of the data distributions used in scatter...
An Algorithm For Finding Entire Solutions Of Systems Of Difference Equations (2003)
Unit Mixte, Nicolas Brisebarre
We present an algorithm that computes the entire solutions of systems of two dierence equations and of systems of one dierential equation and one dierence equation, all with complex polynomials...
Unit Mixte, N. Revol, N. Revol, ...
The goal of this paper is to prove that the implementation of Taylor models in COSY, based on oating-point arithmetic, computes results satisfying the containment property, i.e. guaranteed results.
Study of a Non Intrusive and Accurate Method for Measuring the End-to-End Useful Bandwidth (2003)
Unit Mixte, Mathieu Goutelle, Pascale Primet
Studies and tools development for applications sensitive to data rates is a very active research field for distributed application performance optimization. The research community works to propose...
Scheduling Divisible Loads on Star and Tree Networks: Results and Open Problems (2003)
Unit Mixte, Arnaud Legrand, Olivier Beaumount, ...
Many applications in scientific and engineering domains are structured as large numbers of independent tasks with low granularity. These applications are thus amenable to straightforward...
On The Complexity Of Computing Determinants (2003)
Unit Mixte, Erich Kaltofen, Erich Kaltofen, ...
By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann...
CR-LIBM: The evaluation of the exponential (2003)
Catherine Daramy, David Defour, Jean-Michel Muller, Unit Mixte, ...
We present a new elementary function library, called CR-LIBM. This library implements the various functions defined by the Ansi99 C standard. It provides correctly rounded functions. When writing...
Automatic Deployment of the Network Weather Service Using the Effective Network View (2003)
Unit Mixte, Arnaud Legrand, Arnaud Legr, ...
The monitoring infrastructure constitutes a key component of any Grid middleware. The Network Weather Service (NWS) is the most commonly used tool to fulfill this need. Unfortunately, users have to...
Laboratoire de l'Informatique du Paralllisme (2003)
Cole Normale Suprieure, Unit Mixte, Christoph Quirin, Lauter Novembre, ...
This article presents an ecient implementation of a correctly rounded exponential function in double precision on the Intel Itanium processor family. This work combines advanced processor features...
Scheduling Strategies for Mixed Data and Task Parallelism on Heterogeneous Processor Grids (2002)
Unit Mixte, Olivier Beaumont, Arnaud Legrand, ...
In this paper, we consider the execution of a complex application on a heterogeneous "grid" computing platform. The complex application consists of a suite of identical, independent...
Static Scheduling Strategies for Heterogeneous Systems (2002)
Unit Mixte, O. Beaumont, A. Legrand, ...
In this paper, we consider static scheduling techniques for heterogeneous systems, such as clusters and grids. We successively deal with minimum makespan scheduling, divisible load scheduling and...
Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems (2002)
Unit Mixte, Arnaud Legrand, Olivier Beaumont, ...
In this paper, we discuss several algorithms for scheduling divisible loads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the...
Alexandre Denis March, Unit Mixte, Alexandre Denis
Applications often have to chose between the slow TCP and the unreliable UDP. Robin Kravets from the GaTech has proposed an alternative: the Variable Reliability Protocol (VRP). The applications can...
Generic Distributed Shared Memory: the DSM-PM2 Approach (2000)
Unit Mixte, Gabriel Antoniu, Gabriel Antoniu, ...
This paper describes DSM-PM2, a generic, multi-protocol distributed shared memory library built for PM2, a multithreaded runtime system with preemptive thread migration. DSM-PM2 allows threads...
Listing All Potential Maximal Cliques of a Graph (1999)
Unit Mixte, Vincent Bouchitte, Vincent Bouchitt, ...
A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for...
Loop Shifting for Loop Compaction (1999)
Unit Mixte, Alain Darte, Alain Darte, Guillaume Huard, ...
The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource...
Treewidth and Minimum Fill-in: Grouping the Minimal Separators (1999)
Unit Mixte, Vincent Bouchitte, Vincent Bouchitt, ...
We use the notion of potential maximal clique to characterize the maximal cliques appearing in minimal triangulations of a graph. We show that if these objects can be listed in polynomial time for a...
On the Complexity of Loop Fusion (1998)
Unit Mixte, Alain Darte, Alain Darte
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The...