Search

Your search keyword '"Matthieu Gallet"' showing total 43 results
Start Over Author "Matthieu Gallet"
43 results on '"Matthieu Gallet"'

1. Wet Snow Detection From Satellite SAR Images by Machine Learning With Physical Snowpack Model Labeling

Author

Matthieu Gallet, Abdourrahmane Atto, Fatima Karbou, and Emmanuel Trouve

Subjects
Detection, labeling, synthetic aperture radar (SAR), segmentation, Sentinel-1, snowpack model, Ocean engineering, TC1501-1800, Geophysics. Cosmic physics, QC801-809
Abstract

The detection of wet snow by satellite imaging is currently done in an unsupervised way and lacks quantitative evaluation due to the difficulty of collecting ground truths in extreme environments. In this article, we propose to take into account information associated with a physical model to label satellite data for the purpose of supervised learning of snow properties using synthetic aperture radar (SAR) imagery. This dataset is constructed from Sentinel-1 SAR images, augmented with topographic information obtained from a digital elevation model. The labeling of this data is done at the scale of the Northern Alps using the CROCUS physical snow model. Then, we trained, over 13 combinations of labeled dataset, a wide range of machine learning models to quantitatively identify the most relevant learners for the wet snow detection task. The results demonstrate consistency among the different algorithms, with significant improvement observed when incorporating polarimetric combinations and topographic orientation data in the input of the model. The best algorithmic solution trained on this dataset is evaluated by comparing the obtained wet snow map over a validation area in the French massif of the Grandes Rousses with the existing Copernicus products, fractional snow cover, and SAR wet snow. We also compare the temporal results obtained at one meteorological station located in the test area. The results show a better representation of wet snow during the melting period using the supervised learning approach, as well as a reduction in areas classified as wet during the winter season.

Published
2024
Full Text
View/download PDF

2. Dealing with dry waste disposal issues associated with 177mLu impurities: a long-term challenge for nuclear medicine departments

Author

Sylviane Prevot, Inna Dygaï-Cochet, Jean-Marc Riedinger, Jean-Marc Vrigneaud, Myriam Quermonne, Matthieu Gallet, and Alexandre Cochet

Subjects
177Lu-dotatate, Lutathera®, 177mLu impurities, Storage, Waste, Medical physics. Medical radiology. Nuclear medicine, R895-920
Abstract

Abstract Purpose A strategy for management of radioactive waste associated with 177Lu-dotatate (Lutathera®) treatments was established in our institution, based on predicted storage times of 3–5 years extrapolated from the results of a 2-year measurement study. The aim of this work was to validate this strategy by identifying contaminants and confirming disposal based on the clearance level twice-the-background was within expected time frames. Methods We conducted a prospective series of measurements of radioactive waste associated with the first 65 treatments administered. Sequential measurements of the first 45 vials used were performed on a dose calibrator to identify contaminants. Exposure rates in contact were monitored with a dose ratemeter on a 6-monthly basis for all waste stored: 46 empty vials, 19 vials partially used and 61 biohazard containers. Results Initial median activity of the first vials used was 118 MBq [4–4188 MBq]. For each vial, the decay curve of activity obtained was adjusted to a bi-exponential model. The major component, representing 99.7% of the activity, has a median half-life of 6.6 days [5.7–7.2 days] corresponding to 177Lu. The second, representing only 0.3% of the activity and having a median half-life of 152 days [104–205 days] corresponding to 177mLu, determines necessary storage times. Partially used vials can be disposed of after 5 years, other waste after 3 years. Compliance with the regulatory clearance level is achieved within expected time frames. Conclusion Although only present as traces, 177mLu associated with the direct production route results in major radioactive waste disposal issues for hospitals. Availability of radiopharmaceuticals without impurities appears to be crucial for an expanding use of targeted radionuclide therapy.

Published
2023
Full Text
View/download PDF

4. Impact of contouring methods on pre-treatment and post-treatment dosimetry for the prediction of tumor control and survival in HCC patients treated with selective internal radiation therapy

Author

Guillaume Nodari, Romain Popoff, Jean Marc Riedinger, Olivier Lopez, Julie Pellegrinelli, Inna Dygai-Cochet, Claire Tabouret-Viaud, Benoit Presles, Olivier Chevallier, Sophie Gehin, Matthieu Gallet, Marianne Latournerie, Sylvain Manfredi, Romaric Loffroy, Jean Marc Vrigneaud, and Alexandre Cochet

Subjects
Radioembolization, Hepatocellular carcinoma, Dosimetry, Medical physics. Medical radiology. Nuclear medicine, R895-920
Abstract

Abstract Introduction The aim of this study was to evaluate the impact of the contouring methods on dose metrics and their predictive value on tumor control and survival, in both situations of pre-treatment and post-treatment dosimetry, for patients with advanced HCC treated with SIRT. Methods Forty-eight patients who underwent SIRT between 2012 and 2020 were retrospectively included in this study. Target volumes were delineated using two methods: MRI-based contours manually drawn by a radiologist and then registered on SPECT/CT and PET/CT via deformable registration (Pre-CMRI and Post-CMRI), 99mTc-MAA-SPECT and 90Y-microspheres-PET 10% threshold contouring (Pre-CSPECT and Post-CPET). The mean absorbed dose (Dm) and the minimal absorbed dose delivered to 70% of the tumor volume (D70) were evaluated with both contouring methods; the tumor-to-normal liver uptake ratio (TNR) was evaluated with MRI-based contours only. Tumor response was assessed using the mRECIST criteria on the follow-up MRIs. Results No significant differences were found for Dm and TNR between pre- and post-treatment. TNR evaluated with radiologic contours (Pre-CMRI and Post-CMRI) were predictive of tumor control at 6 months on pre- and post-treatment dosimetry (OR 5.9 and 7.1, respectively; p = 0.02 and 0.01). All dose metrics determined with both methods were predictive of overall survival (OS) on pre-treatment dosimetry, but only Dm with MRI-based contours was predictive of OS on post-treatment images with a median of 23 months for patients with a supramedian Dm versus 14 months for the others (p = 0.04). Conclusion In advanced HCC treated with SIRT, Dm and TNR determined with radiologic contours were predictive of tumor control and OS. This study shows that a rigorous clinical workflow (radiologic contours + registration on scintigraphic images) is feasible and should be prospectively considered for improving therapeutic strategy.

Published
2021
Full Text
View/download PDF

7. Learning Spatiotemporal Occupancy Grid Maps for Lifelong Navigation in Dynamic Scenes

Author

Thomas, Hugues, Aurin, Matthieu Gallet de Saint, Zhang, Jian, and Barfoot, Timothy D.

Subjects
Computer Science - Robotics
Abstract

We present a novel method for generating, predicting, and using Spatiotemporal Occupancy Grid Maps (SOGM), which embed future information of dynamic scenes. Our automated generation process creates groundtruth SOGMs from previous navigation data. We build on prior work to annotate lidar points based on their dynamic properties, which are then projected on time-stamped 2D grids: SOGMs. We design a 3D-2D feedforward architecture, trained to predict the future time steps of SOGMs, given 3D lidar frames as input. Our pipeline is entirely self-supervised, thus enabling lifelong learning for robots. The network is composed of a 3D back-end that extracts rich features and enables the semantic segmentation of the lidar frames, and a 2D front-end that predicts the future information embedded in the SOGMs within planning. We also design a navigation pipeline that uses these predicted SOGMs. We provide both quantitative and qualitative insights into the predictions and validate our choices of network design with a comparison to the state of the art and ablation studies.

Published
2021

15. Démarche d’optimisation des modalités de gestion des déchets lors des traitements au 177Lu-oxodotréotide (Lutathera®)

Author

M. Silvestre, M. Quermonne, Matthieu Gallet, Alexandre Cochet, S. Prévot, N. Baptista, Inna Dygai-Cochet, A. Nicolas, L. Lavergnas, J.M. Riedinger, and Jean-Marc Vrigneaud

Subjects
Radiological and Ultrasound Technology, Biophysics, Radiology, Nuclear Medicine and imaging
Abstract

Resume Cette etude propose un retour d’experience sur les modalites de gestion et d’elimination des dechets contamines au Lutetium-177 (177Lu, Lu-177) instaurees dans le cadre des procedures de radiotherapie interne vectorisee au 177Lu-oxodotreotide (Lutathera®). Les traitements sont administres dans un box dedie du service de medecine nucleaire ou tous les dechets solides sont tries et collectes dans des contenants appropries. Des durees previsionnelles de stockage ont ete extrapolees a partir des resultats d’une campagne de mesures iteratives sur deux ans. Les effluents radioactifs des eviers chauds se deversent dans des cuves, dont l’activite volumique mesuree a la fermeture permet de calculer la duree d’entreposage avant vidange. L’activite du Lu-177 elimine par excretion renale dans les 6 heures qui suivent la fin de la perfusion du medicament radiopharmaceutique a ete evaluee a partir de l’analyse de prelevements urinaires. Les premieres mictions sont dirigees vers trois fosses tampons dont l’efficacite a ete estimee en comparant l’activite du Lu-177 qui entre dans le dispositif a celle qui en sort. Les resultats des controles semestriels, effectues par mesure en continu de l’activite volumique des effluents aux emissaires, ont permis d’evaluer la fraction de l’activite annuelle administree finalement rejetee dans les eaux usees et de definir des valeurs guides. L’impact des deversements radioactifs de l’etablissement sur l’exposition annuelle des travailleurs du reseau d’assainissement a ete quantifie avec l’outil de Calcul de l’Impact des Deversements Radioactifs dans les REseaux (CIDRRE) developpe par l’Institut de radioprotection et de surete nucleaire (IRSN).

Published
2021
Full Text
View/download PDF

27. Impact of contouring methods on pre-treatment and post-treatment dosimetry for the prediction of tumor control and survival in HCC patients treated with selective internal radiation therapy

Author

Benoit Presles, Jean Marc Riedinger, Sophie Gehin, Jean Marc Vrigneaud, Alexandre Cochet, Romaric Loffroy, Olivier Lopez, Marianne Latournerie, Olivier Chevallier, Matthieu Gallet, Julie Pellegrinelli, Inna Dygai-Cochet, Romain Popoff, Sylvain Manfredi, Guillaume Nodari, and Claire Tabouret-Viaud

Subjects
lcsh:Medical physics. Medical radiology. Nuclear medicine, Contouring, business.industry, Hepatocellular carcinoma, lcsh:R895-920, Selective internal radiation therapy, Tumor control, medicine.disease, 030218 nuclear medicine & medical imaging, 03 medical and health sciences, 0302 clinical medicine, 030220 oncology & carcinogenesis, Absorbed dose, Dosimetry, Medicine, Radiology, Nuclear Medicine and imaging, Post treatment, Radioembolization, business, Nuclear medicine, Cardiac imaging, Original Research
Abstract

Introduction The aim of this study was to evaluate the impact of the contouring methods on dose metrics and their predictive value on tumor control and survival, in both situations of pre-treatment and post-treatment dosimetry, for patients with advanced HCC treated with SIRT. Methods Forty-eight patients who underwent SIRT between 2012 and 2020 were retrospectively included in this study. Target volumes were delineated using two methods: MRI-based contours manually drawn by a radiologist and then registered on SPECT/CT and PET/CT via deformable registration (Pre-CMRI and Post-CMRI), 99mTc-MAA-SPECT and 90Y-microspheres-PET 10% threshold contouring (Pre-CSPECT and Post-CPET). The mean absorbed dose (Dm) and the minimal absorbed dose delivered to 70% of the tumor volume (D70) were evaluated with both contouring methods; the tumor-to-normal liver uptake ratio (TNR) was evaluated with MRI-based contours only. Tumor response was assessed using the mRECIST criteria on the follow-up MRIs. Results No significant differences were found for Dm and TNR between pre- and post-treatment. TNR evaluated with radiologic contours (Pre-CMRI and Post-CMRI) were predictive of tumor control at 6 months on pre- and post-treatment dosimetry (OR 5.9 and 7.1, respectively; p = 0.02 and 0.01). All dose metrics determined with both methods were predictive of overall survival (OS) on pre-treatment dosimetry, but only Dm with MRI-based contours was predictive of OS on post-treatment images with a median of 23 months for patients with a supramedian Dm versus 14 months for the others (p = 0.04). Conclusion In advanced HCC treated with SIRT, Dm and TNR determined with radiologic contours were predictive of tumor control and OS. This study shows that a rigorous clinical workflow (radiologic contours + registration on scintigraphic images) is feasible and should be prospectively considered for improving therapeutic strategy.

Published
2021

28. Learning Spatiotemporal Occupancy Grid Maps for Lifelong Navigation in Dynamic Scenes

Author

Thomas, Hugues, Aurin, Matthieu Gallet de Saint, Zhang, Jian, and Barfoot, Timothy D.

Subjects
Computer Science - Robotics
Abstract

We present a novel method for generating, predicting, and using Spatiotemporal Occupancy Grid Maps (SOGM), which embed future information of dynamic scenes. Our automated generation process creates groundtruth SOGMs from previous navigation data. We build on prior work to annotate lidar points based on their dynamic properties, which are then projected on time-stamped 2D grids: SOGMs. We design a 3D-2D feedforward architecture, trained to predict the future time steps of SOGMs, given 3D lidar frames as input. Our pipeline is entirely self-supervised, thus enabling lifelong learning for robots. The network is composed of a 3D back-end that extracts rich features and enables the semantic segmentation of the lidar frames, and a 2D front-end that predicts the future information embedded in the SOGMs within planning. We also design a navigation pipeline that uses these predicted SOGMs. We provide both quantitative and qualitative insights into the predictions and validate our choices of network design with a comparison to the state of the art and ablation studies.

Published
2022
Full Text
View/download PDF

29. Effect of 99mTc elution in vivo from red cells on red cell volumes measured using autologous 99mTc-labeled red cells: comparison with 51Cr method

Author

Alexandra Nicolas, Matthieu Gallet, François Girodon, Clément Drouet, and Jean-Marc Riedinger

Subjects
chemistry.chemical_compound, chemistry, Elution, Sodium, Radiochemistry, chemistry.chemical_element, General Medicine, Red cell volume, Sodium pertechnetate
Abstract

The purpose of this work was to compare the measured red-cell volume (RCV) using sodium pertechnetate [RCV-99mTc] compared to the reference technique using sodium radiochromate [RCV-51Cr] and to assess the influence of technetium-99 elution on the RCV-99mTc value. Ten patients had simultaneous measurements of RCV-99mTc and RCV-51Cr. Elution of Tc-99m from red blood cells was 2.9% and led to an average overestimation of RCV-99mTc of 3.7%. The introduction of individual tracer elution rates in the RCV-99mTc calculation corrects this overestimation.

Published
2020
Full Text
View/download PDF

31. Dealing with dry waste disposal issues associated with

Author

Sylviane, Prevot, Inna, Dygaï-Cochet, Jean-Marc, Riedinger, Jean-Marc, Vrigneaud, Myriam, Quermonne, Matthieu, Gallet, and Alexandre, Cochet

Abstract

A strategy for management of radioactive waste associated withWe conducted a prospective series of measurements of radioactive waste associated with the first 65 treatments administered. Sequential measurements of the first 45 vials used were performed on a dose calibrator to identify contaminants. Exposure rates in contact were monitored with a dose ratemeter on a 6-monthly basis for all waste stored: 46 empty vials, 19 vials partially used and 61 biohazard containers.Initial median activity of the first vials used was 118 MBq [4-4188 MBq]. For each vial, the decay curve of activity obtained was adjusted to a bi-exponential model. The major component, representing 99.7% of the activity, has a median half-life of 6.6 days [5.7-7.2 days] corresponding toAlthough only present as traces

Published
2021

32. Smartphone-based application and nurses’ interventions for symptoms monitoring in patients treated with oral anticancer agents: A 1-year follow-up in a tertiary cancer center

Author

Laura Porcher, Valérie Perron, Julie Blanc, Courèche-Guillaume Kaderbhai, Zoé Tharin, Antonin Schmitt, and Matthieu Gallet

Subjects
Oncology, Pharmacology (medical)
Abstract

Aim The increasing use of oral anticancer agents over the past years has necessitated changes in monitoring toxicities to ensure patients’ adherence and tolerance at home. The aim of this study was to describe nurses’ interventions and medical changes after alerts triggered by a web-based platform designed to support the management of oral anticancer agents-related toxicities. Methods This retrospective study included patients undergoing oral anticancer agents in a cancer center from September 2018 to September 2019 (excluding hormonal therapy). In this cancer center, the standard of care included symptoms’ collections for 1 month thanks to a web platform based on patient-reported outcomes. Patients had to fill a weekly questionnaire (Q1 to Q4). The web-based platform triggered orange alerts when patients reported moderate symptoms and red alerts when severe toxicities were declared. The rate of orange and red alerts, the rate of patients with medical changes consecutively to an orange or a red alert, and the different types of nurses’ interventions and medical changes were assessed. Results A total of 524 patients were extracted but the final number of 436 patients were included in this study and 1488 questionnaires were filled in. More than 90% of patients declared that they took their medication as prescribed. Up to 60% of patients recorded all grade symptoms, including 8% of patients who recorded Grades 3–4 symptoms during the month, mostly anorexia, fatigue, and diarrhea. The web platform system triggered 700 orange and 212 red alerts: 305/700 (44%) of orange alerts resulted in nurses’ interventions, most frequently phone counseling (78%), and 65/212 (31%) of red alerts resulted in medical changes, most frequent treatment interruptions (48%). Conclusion Implementing an e-health (electronic-health) system can be helpful for monitoring symptoms in patients under oral anticancer agents, enhancing that this organization should be a standard of care in every cancer centers.

Published
2022
Full Text
View/download PDF

33. [Effect of obesity, age and gender on glomerular filtration rate measured in normal adults]

Author

Alexandre Cochet, Alina Berriolo-Riedinger, Clément Drouet, Jean-Marc Riedinger, Alexandra Nicolas, and Matthieu Gallet

Subjects
Adult, Male, medicine.medical_specialty, Urology, Renal function, Normal values, urologic and male genital diseases, Kidney, Age and gender, medicine, Humans, Obesity, Edetic Acid, Retrospective Studies, Body surface area, urogenital system, business.industry, Retrospective cohort study, General Medicine, Nomogram, medicine.disease, female genital diseases and pregnancy complications, medicine.anatomical_structure, Female, business, Glomerular Filtration Rate
Abstract

The aims of this study were to assess the dependence of glomerular filtration rate (GFR) on age and gender and to produce reference data for the interpretation of 51Cr-EDTA GFR measurements in adults. METHODS This was a retrospective study of 120 live kidney donors (75 females, 45 males). GFR was evaluated from 51Cr-EDTA plasma clearance using blood samples taken at 3, 4 and 5 hours. The slope-intercept GFR was corrected for body surface area using the Dubois & Dubois and for the fast exponential using the Brochner-Mortensen equation. Scatter plot of DFG against age in live kidney donors was plotted and the 98% range limits have been defined. RESULTS The median GFR obtained for kidney donors was 88 mL/min/1.73 m2 [68-130]. No significant difference with gender was found. 51Cr-EDTA clearance was strongly correlated with patient age (r = - 0.62, P

Published
2021

34. [Effect of

Author

Matthieu, Gallet, Clément, Drouet, François, Girodon, Alexandra, Nicolas, and Jean-Marc, Riedinger

Subjects
Adult, Aged, 80 and over, Male, Radioisotope Dilution Technique, Erythrocytes, Dose-Response Relationship, Drug, Technetium, Middle Aged, Chromium Radioisotopes, Hematocrit, Isotope Labeling, Erythrocyte Count, Humans, Female, Aged, Erythrocyte Volume
Abstract

The purpose of this work was to compare the measured red-cell volume (RCV) using sodium pertechnétate [RCV

Published
2020

36. Computing the throughput of probabilistic and replicated streaming applications

Author

Anne Benoit, Matthieu Gallet, Bruno Gaujal, Yves Robert, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Middleware efficiently scalable (MESCAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL)

Subjects
0209 industrial biotechnology, Theoretical computer science, General Computer Science, Computer science, Applied Mathematics, Computation, Probabilistic logic, 02 engineering and technology, 01 natural sciences, Computer Science Applications, Set (abstract data type), 010104 statistics & probability, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], 020901 industrial engineering & automation, Bounded function, Theory of computation, Graph (abstract data type), 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Random variable, Algorithm, Throughput (business)
Abstract

In this paper, we investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain; (ii) a one-to-many mapping of the application onto a fully heterogeneous target platform, where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors; and (iii) a set of random variables modeling the computation and communication times in the mapping. We show how to compute the throughput of the application, i.e., the rate at which data sets can be processed. The problem is easy when application stages are not replicated, i.e., each application stage is assigned to a single processor: in that case the throughput is dictated by the critical hardware resource. However, when stages are replicated, i.e., each application stage may be assigned to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput. The first contribution of the paper is to provide a general method to compute the throughput when computation and communication times, also called stage parameters, are constant or follow I.I.D. exponential laws. The second contribution is to provide bounds for the throughput when stage parameters form associated random sequences (correlation between communication and processing times of a given data set on the different application stages, i.e., a data set that takes a long time on the first stage is likely to be large, and to take a long time on the next stages), and are N.B.U.E. (New Better than Used in Expectation) variables (if an operation has already been processed for some duration, the remaining time is smaller than the processing time of a fresh operation): the throughput is bounded from below by the exponential case and bounded from above by the deterministic case. An extensive set of simulation allows us to assess the quality of the model, and to observe the actual behavior of several distributions.

Published
2013

37. Scheduling complex streaming applications on the Cell processor

Author

Mathias Jacquelin, Matthieu Gallet, Loris Marchal, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Linear programming, Computer science, Processor scheduling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Parallel computing, mixed linear programming, Application software, computer.software_genre, 01 natural sciences, scheduling complex streaming applications, Scheduling (computing), multicore processor, 0202 electrical engineering, electronic engineering, information engineering, streaming applications, Embedded computing, 020203 distributed computing, Multi-core processor, Scheduling, multicore, Ranging, Video on demand, Throughput, multiprocessing systems, Multicore processing, optimal solution, Grid computing, Streaming media, 010201 computation theory & mathematics, Embedding, STI cell BE processor, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Laboratories, Encoder, computer, NP-complete problems, cell processor
Abstract

International audience; In this paper, we consider the problem of scheduling streaming applications described by complex task graphs on a heterogeneous multicore processor, the STI Cell BE processor. We first present a theoretical model of the Cell processor. Then, we use this model to express the problem of maximizing the throughput of a streaming application on this processor. Although the problem is proven NP-complete, we present an optimal solution based on mixed linear programming. This allows us to compute the optimal mapping for a number of applications, ranging from a real audio encoder to complex random task graphs. These mappings are then tested on two platforms embedding Cell processors, and compared to simple heuristic solutions. We show that we are able to achieve a good speed-up, whereas the heuristic solutions generally fail to deal with the strong memory and communication constraints.

Published
2010
Full Text
View/download PDF

38. Computing the throughput of probabilistic and replicated streaming applications

Author

Matthieu Gallet, Fanny Dufossé, Bruno Gaujal, Yves Robert, Anne Benoit, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Middleware efficiently scalable (MESCAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF), and INRIA

Subjects
020203 distributed computing, replication, Markov chain, Computer science, Scheduling, Computation, Probabilistic logic, probabilistic streaming applications, 02 engineering and technology, Parallel computing, Petri net, 01 natural sciences, Polynomial algorithm, Exponential function, Scheduling (computing), 010104 statistics & probability, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, ACM: C.: Computer Systems Organization/C.4: PERFORMANCE OF SYSTEMS/C.4.5: Reliability, availability, and serviceability, 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, throughput, timed Petri nets
Abstract

International audience; In this paper, we investigate how to compute the throughput of probabilistic and replicated streaming applications. We are given (i) a streaming application whose dependence graph is a linear chain; (ii) a one-to-many mapping of the application onto a fully heterogeneous target, where a processor is assigned at most one application stage, but where a stage can be replicated onto a set of processors; and (iii) a set of IID (Independent and Identically-Distributed) variables to model each computation and communication time in the mapping. How can we compute the throughput of the application, i.e., the rate at which data sets can be processed? We consider two execution models, the STRICT model where the actions of each processor are sequentialized, and the OVERLAP model where a processor can compute and communicate in parallel. The problem is easy when application stages are not replicated, i.e., assigned to a single processor: in that case the throughput is dictated by the critical hardware resource. However, when stages are replicated, i.e., assigned to several processors, the problem becomes surprisingly complicated: even in the deterministic case, the optimal throughput may be lower than the smallest internal resource throughput. To the best of our knowledge, the problem has never been considered in the probabilistic case. The first main contribution of the paper is to provide a general method (although of exponential cost) to compute the throughput when mapping parameters follow IID exponential laws. This general method is based upon the analysis of timed Petri nets deduced from the application mapping; it turns out that these Petri nets exhibit a regular structure in the OVERLAP model, thereby enabling to reduce the cost and provide a polynomial algorithm. The second main contribution of the paper is to provide bounds for the throughput when stage parameters are arbitrary IID and NBUE (New Better than Used in Expectation) variables: the throughput is bounded from below by the exponential case and bounded from above by the deterministic case.

Published
2010
Full Text
View/download PDF

39. Efficient Scheduling of Task Graph Collections on Heterogeneous Resources

Author

Loris Marchal, Frédéric Vivien, Matthieu Gallet, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
020203 distributed computing, Schedule, Theoretical computer science, Linear programming, Computer science, Heuristic, Distributed computing, Processor scheduling, Graph theory, 02 engineering and technology, computer.software_genre, Application software, Grid, Scheduling (computing), Workflow, Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, Heuristics, computer
Abstract

International audience; In this paper, we focus on scheduling jobs on computing grids. In our model, a grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a collection of task graphs problem. We are looking for a competitive scheduling algorithm not requiring complex control. We thus only consider single-allocation strategies. In addition to a mixed linear programming approach to find an optimal allocation, we present different heuristic schemes. Then, using simulations, we compare the performance of our different heuristics to the performance of a classical scheduling policy in Grids, HEFT. The results show that some of our static-scheduling policies take advantage of their platform and application knowledge and outperform HEFT, especially under communication-intensive scenarios. In particular, one of our heuristics, DELEGATE, almost always achieves the best performance while having lower running times than HEFT.

Published
2009
Full Text
View/download PDF

40. Computing the throughput of replicated workflows on heterogeneous platforms

Author

Yves Robert, Bruno Gaujal, Anne Benoit, Matthieu Gallet, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Middleware efficiently scalable (MESCAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), ANR-07-BLAN-0192,StochaGrid,Scheduling algorithms and stochastic performance models for workflow applications on dynamic grid platforms(2007), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)

Subjects
Timed Petri nets, Critical resource, Computational complexity theory, Computer science, Scheduling, Distributed computing, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, Petri net, 01 natural sciences, Scheduling (computing), Workflows, Heterogeneous platforms, Workflow, 010201 computation theory & mathematics, 020204 information systems, Period, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; In this paper, we focus on computing the throughput of replicated workflows. Given a streaming application whose dependence graph is a linear chain, and a mapping of this application onto a fully heterogeneous platform, how can we compute the optimal throughput, or equivalently the minimal period? The problem is easy when workflow stages are not replicated, i.e., assigned to a single processor: in that case the period is dictated by the critical hardware resource. But when stages are replicated, i.e., assigned to several processors, the problem gets surprisingly complicated, and we provide examples where the optimal period is larger than the largest cycle-time of any resource. We then show how to model the problem as a timed Petri net to compute the optimal period in the general case, and we provide a polynomial algorithm for the one-port communication model with overlap. Finally, we report comprehensive simulation results on the gap between the optimal period and the largest resource cycle-time.

Published
2009
Full Text
View/download PDF

41. Allocating Series of Workflows on Computing Grids

Author

Frédéric Vivien, Matthieu Gallet, Loris Marchal, Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Job scheduler, 020203 distributed computing, 0303 health sciences, Schedule, Linear programming, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Grid, computer.software_genre, Scheduling (computing), 03 medical and health sciences, Workflow, Grid computing, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Graph (abstract data type), Resource management, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, computer, ComputingMilieux_MISCELLANEOUS, 030304 developmental biology
Abstract

In this report, we focus on scheduling jobs on computing Grids. In our model, a Grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a series of workflow problem. We are looking for an efficient solution with regard to throughput and latency, while avoiding solutions requiring complex control. We thus only consider single-allocation strategies. We present an algorithm based on mixed linear programming to find an optimal allocation, and this for different routing policies depending on how much latitude we have on communications. Then, using simulations, we compare our allocations to reference heuristics. Our results show that our algorithm almost always finds an allocation with good throughput and low latency, and that it outperforms the reference heuristics, especially under communication-intensive scenarios.

Published
2008
Full Text
View/download PDF

42. Scheduling multiple divisible loads on a linear processor network

Author

Yves Robert, Matthieu Gallet, Frédéric Vivien, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
FOS: Computer and information sciences, 020203 distributed computing, Mathematical optimization, Linear programming, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.5: Sequencing and scheduling, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Execution time, Scheduling (computing), Computer Science - Distributed, Parallel, and Cluster Computing, Linear algebra, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, Distributed, Parallel, and Cluster Computing (cs.DC), 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

Min, Veeravalli, and Barlas have recently proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal schedule for any instance, once the number of installments per load is given. Then, we formally state that any optimal schedule has an infinite number of installments under a linear cost model as the one assumed in the original papers. Therefore, such a cost model cannot be used to design practical multi-installment strategies. Finally, through extensive simulations we confirmed that the best solution is always produced by the linear programming approach, while solutions of the original papers can be far away from the optimal.

Published
2007
Full Text
View/download PDF

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

Author

Frédéric Vivien, Matthieu Gallet, Yves Robert, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'informatique du parallélisme, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Algorithms and Scheduling for Distributed Heterogeneous Platforms (GRAAL), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Earliest deadline first scheduling, Rate-monotonic scheduling, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 0102 computer and information sciences, 02 engineering and technology, Dynamic priority scheduling, 01 natural sciences, Fair-share scheduling, GeneralLiterature_MISCELLANEOUS, Grille de calcul, Fixed-priority pre-emptive scheduling, stomatognathic system, [INFO]Computer Science [cs], Complexité, Communication complexity, ComputingMilieux_MISCELLANEOUS, ComputingMethodologies_COMPUTERGRAPHICS, Ordonnancement de transfert de fichiers, 021103 operations research, Complexity, Switch, Round-robin scheduling, Scheduling file transfers, stomatognathic diseases, ComputingMethodologies_PATTERNRECOGNITION, 010201 computation theory & mathematics, Two-level scheduling, Grid computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Networks, Réseaux, Algorithm, Commutateur
Abstract

In this paper, we study the problem of scheduling file transfers through aswitch. This problem is at the heart of a model often used for large grid computations,where the switch represents the core of the network interconnectingthe various clusters that compose the grid. We establish several complexityresults, and we introduce and analyze various algorithms, from both a theoreticaland a practical perspective.; Dans ce rapport, nous étudions l’ordonnancement de l’envoi de fichiers à travers un switch. Ce problème est souvent utilisé pour modéliser le réseau utilisé par une grille de calcul, où le switch représente le cœur du réseau qui relie les différents clusters composant la grille. Nous établissons différents résultats de complexité, avant d’étudier plusieurs algorithmes, tant d’un point de vue théorique que d’un point de vue pratique.

Published
2006
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results