Search

Showing total 8 results
Start Over Topic algorithm Language english
8 results

1. Programming Strategies for Irregular Algorithms on the Emu Chick

Author

Jiajia Li, Ümit V. Çatalyürek, Rich Vuduc, Jeffrey Young, Bora Uçar, Eric R. Hein, Abdurrahman Yasar, Srinivas Eswar, Jason Riedy, Thomas M. Conte, Emu Technology, Georgia Institute of Technology [Atlanta], Pacific Northwest National Laboratory (PNNL), 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), É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), This work partially was supported by NSF Grant ACI-1339745 (XScala), an IARPA contract, and the Defense Advanced Research Projects Agency (DARPA) under agreement #HR0011-13-2-0001. Any opinions, findings, conclusions, or recommendations in this paper are solely those of the authors and do not necessarily reflect the position or the policy of the sponsors. Thanks also to the Emu Technology team for support and debugging assistance with the Emu Chick prototype, and to the reviewers for their thoughtful comments., É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, 0301 basic medicine, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Memory bandwidth, 02 engineering and technology, Thread (computing), 020202 computer hardware & architecture, Computer Science Applications, 03 medical and health sciences, 030104 developmental biology, Computational Theory and Mathematics, Application-specific integrated circuit, Computer Science - Distributed, Parallel, and Cluster Computing, Hardware and Architecture, Modeling and Simulation, 0202 electrical engineering, electronic engineering, information engineering, Graph alignment, Bandwidth (computing), Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Field-programmable gate array, Algorithm, Software, Analysis of algorithms
Abstract

The Emu Chick prototype implements migratory memory-side processing in a novel hardware system. Rather than transferring large amounts of data across the system interconnect, the Emu Chick moves lightweight thread contexts to near-memory cores before the beginning of each remote memory read. Previous work has characterized the performance of the Chick prototype in terms of memory bandwidth and programming differences from more typical, non-migratory platforms, but there has not yet been an analysis of algorithms on this system. This work evaluates irregular algorithms that could benefit from the lightweight, memory-side processing of the Chick and demonstrates techniques and optimization strategies for achieving performance in sparse matrix-vector multiply operation (SpMV), breadth-first search (BFS), and graph alignment across up to eight distributed nodes encompassing 64 nodelets in the Chick system. We also define and justify relative metrics to compare prototype FPGA-based hardware with established ASIC architectures. The Chick currently supports up to 68x scaling for graph alignment, 80 MTEPS for BFS on balanced graphs, and 50% of measured STREAM bandwidth for SpMV.

Published
2020

2. The fast iterated bootstrap

Author

Mirza Trokic, Russell Davidson, McGill University = Université McGill [Montréal, Canada], Centre interuniversitaire de recherche en économie quantitative (CIREQ), Aix-Marseille Sciences Economiques (AMSE), École des hautes études en sciences sociales (EHESS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), IHS Markit, and This research was supported by the Canada Research Chair program (Chair in Economics, McGill University), and by grants from the Social Sciences and Humanities Research Council of Canada and the Fonds de Recherche du QuebecSociete Culture, Canada. We are grateful to seminar participants at the Third French Econometric Conference, the Singapore Management University, the Hong Kong University of Science and Technology, and the University of Sydney, for useful comments. We also thank our discussant Matt Webb for insightful comments at the 2017 CESG. Our thanks go to three anonymous referees and a guest co-editor for insightful comments that helped us improve the paper.

Subjects
Economics and Econometrics, Series (mathematics), Computer science, Applied Mathematics, 05 social sciences, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C12 - Hypothesis Testing: General, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C10 - General, Sense (electronics), [SHS.ECO]Humanities and Social Sciences/Economics and Finance, 01 natural sciences, Power (physics), Bootstrap iteration Fast iterated bootstrap, 010104 statistics & probability, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, Null (SQL), Iterated function, Distortion, 0502 economics and business, bootstrap iteration, fast iterated bootstrap, JEL: C - Mathematical and Quantitative Methods/C.C1 - Econometric and Statistical Methods and Methodology: General/C.C1.C15 - Statistical Simulation Methods: General, 0101 mathematics, Algorithm, 050205 econometrics
Abstract

International audience; The standard forms of bootstrap iteration are very computationally demanding. As a result, there have been several attempts to alleviate the computational burden by use of approximations. In this paper, we extend the fast double bootstrap of Davidson and MacKinnon (2007) to higher orders of iteration, and provide algorithms for their implementation. The new methods make computational demands that increase only linearly with the level of iteration, unlike standard procedures, whose demands increase exponentially. In a series of simulation experiments, we show that the fast triple bootstrap improves on both the standard and fast double bootstraps, in the sense that it suffers from less size distortion under the null with no accompanying loss of power.

Published
2020

3. Multi-fidelity modeling with different input domain definitions using Deep Gaussian Processes

Author

Nouredine Melab, El-Ghazali Talbi, Ali Hebbal, Mathieu Balesdent, Loïc Brevault, DTIS, ONERA, Université Paris Saclay [Palaiseau], ONERA-Université Paris-Saclay, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), and The work of Ali Hebbal is a funded by ONERA - The French Aerospace Lab and the University of Lille through a PhD thesis. This work is also part of two projects (HERACLES and MUFIN) funded by ONERA. The Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

Subjects
FOS: Computer and information sciences, Domain of a function, Computer Science - Machine Learning, Control and Optimization, Computer science, media_common.quotation_subject, 0211 other engineering and technologies, Fidelity, Machine Learning (stat.ML), 02 engineering and technology, Machine Learning (cs.LG), Domain (software engineering), symbols.namesake, 0203 mechanical engineering, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, multifidélité, modélisation bayésienne, Gaussian process, 021106 design practice & management, media_common, business.industry, Quantum Physics, Computer Graphics and Computer-Aided Design, Computer Science Applications, 020303 mechanical engineering & transports, Test case, Control and Systems Engineering, espace entree dimension variée, symbols, Global Positioning System, Engineering design process, business, Parametrization, Algorithm, Software, processus gaussien
Abstract

International audience; Multi-fidelity approaches combine different models built on a scarce but accurate data-set (high-fidelity data-set), and a large but approximate one (low-fidelity data-set) in order to improve the prediction accuracy. Gaussian Processes (GPs) are one of the popular approaches to exhibit the correlations between these different fidelity levels. Deep Gaussian Processes (DGPs) that are functional compositions of GPs have also been adapted to multi-fidelity using the Multi-Fidelity Deep Gaussian process model (MF-DGP). This model increases the expressive power compared to GPs by considering non-linear correlations between fidelities within a Bayesian framework. However, these multi-fidelity methods consider only the case where the inputs of the different fidelity models are defined over the same domain of definition (e.g., same variables, same dimensions). However, due to simplification in the modeling of the low-fidelity, some variables may be omitted or a different parametrization may be used compared to the high-fidelity model. In this paper, Deep Gaussian Processes for multi-fidelity (MF-DGP) are extended to the case where a different parametrization is used for each fidelity. The performance of the proposed multifidelity modeling technique is assessed on analytical test cases and on structural and aerodynamic real physical problems.

Published
2020

4. On the Performance of Sliding Window TD-LMMSE Channel Estimation for 5G Waveforms in High Mobility Scenario

Author

Marion Berbineau, Iyad Dayoub, Michel Saideh, Département Composants et Systèmes (IFSTTAR/COSYS), Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université de Lyon-PRES Université Nantes Angers Le Mans (UNAM)-PRES Université Lille Nord de France, Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), COMmunications NUMériques - IEMN (COMNUM - IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France), Institut National des Sciences Appliquées (INSA), This work was supported in part by the SMARTIES project within theELSAT2020 program supported by FEDER, the French State, and the Haut deFrance Region and in part by the X2RAIL-1 project from H2020 SHIF2RAILprogram. The review of this paper was coordinated by Dr. N.-D. Dao., PRES Université Lille Nord de France-PRES Université Nantes Angers Le Mans (UNAM)-Université de Lyon-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)

Subjects
CHANNEL ESTIMATION, Computer Networks and Communications, Orthogonal frequency-division multiplexing, Computer science, Monte Carlo method, Aerospace Engineering, 02 engineering and technology, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], TRAITEMENT DU SIGNAL, TECHNOLOGIE SANS FIL, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], TELECOMMUNICATION, LMMSE, Sliding window protocol, 0202 electrical engineering, electronic engineering, information engineering, Waveform, [INFO]Computer Science [cs], Time domain, Electrical and Electronic Engineering, ONDE, Computer Science::Information Theory, 020208 electrical & electronic engineering, 020206 networking & telecommunications, FBMC, Filter bank, Computer Science::Other, [SPI.TRON]Engineering Sciences [physics]/Electronics, TRANSPORT FERROVIAIRE, Modulation, Automotive Engineering, SIMULATION, Algorithm, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, 5G, Communication channel
Abstract

The upcoming 5G era is considered as a critical answer to future railway communication needs. In this correspondence, we analyze the performance of sliding window time domain (TD) LMMSE channel estimation technique where a generalized development is proposed and analyzed for 5G filter bank multicarrier-offset quadratic-amplitude modulation waveform candidates. In order to enhance performance, the analytical model is extended to exploit multipaths and multiantennas correlation wherever they do exist e.g., tunnels. TD-LMMSE performance for 5G waveforms and achieved enhancements are verified by Monte Carlo simulations.

Published
2018

5. Checksum-Filtered List Decoding Applied to H.264 and H.265 Video Error Correction

Author

Patrick Corlay, Stephane Coulombe, Firouzeh Golaghazadeh, François-Xavier Coudoux, Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), COMmunications NUMériques - IEMN (COMNUM - IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), This work was supported by the Natural Sciences and Engineering Research Council of Canada Discovery Grant. This paper was recommended by Associate Editor Siwei Ma, Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)

Subjects
Computer science, Real-time computing, List decoding, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, Smacker video, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], "Video Transmission", [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], "H.265", 0202 electrical engineering, electronic engineering, information engineering, Media Technology, [INFO]Computer Science [cs], Electrical and Electronic Engineering, Bitstream, Motion compensation, "List Decoding", Network packet, "Video Error Correction", 020206 networking & telecommunications, computer.file_format, Coding tree unit, Scalable Video Coding, [SPI.TRON]Engineering Sciences [physics]/Electronics, "High Efficiency Video Coding (HEVC)", "H.264", Checksum, "Checksum", 020201 artificial intelligence & image processing, Multiview Video Coding, Error detection and correction, Algorithm, computer, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

JIF=4.046; International audience; The latest video coding standards, H.264 and H.265, are highly vulnerable in error-prone networks. Reconstructed packets may exhibit significant degradation in terms of peak signal-to-noise ratio and visual quality. This paper presents a novel list-decoding approach exploiting the receiver side user datagram protocol (UDP) checksum. The proposed method identifies the possible locations of errors by analyzing the pattern of the calculated UDP checksum. This permits considerably reducing the number of candidate bitstreams in comparison to conventional list decoding approaches. When a packet composed of N bits contains a single-bit error, instead of considering N candidate bitstreams, as is the case in conventional list decoding approaches, the proposed approach considers N/32 candidate bitstreams, leading to a reduction of 97% of the number of candidates. For a two-bit error, the reduction increases to 99.6%. The method's performance is evaluated using H.264 and H.265 test model software. Our simulation results reveal that, on average, the error was corrected perfectly 80%-90% of the time (the original bitstream was recovered). In addition, the proposed approach provides, on average, a 2.79-dB gain over frame copy (FC) error concealment using the joint model and a 3.57-dB gain over our implementation of FC error concealment in the High Efficiency Video Coding test model.

Published
2018

6. Dislocation detection in field environments: A belief functions contribution

Author

Carl T. Haas, Saiedeh Razavi, Emmanuel Duflos, Philippe Vanheeghe, Department of Civil and Environmental Engineering [Waterloo], University of Waterloo [Waterloo], Sequential Learning (SEQUEL), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), LAGIS-SI, Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), The research work was sponsored by a CNRS International Scientific Collaboration Program (PICS)., This paper results from the collaboration between the Laboratoire d'Automatique Génie Informatique et Signal (UMR CNRS 8219, Lille, France) and the Department of Civil and Environmental Engineering of the University of Waterloo (Canada)., Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Automatique, Génie Informatique et Signal (LAGIS), and Université de Lille, Sciences et Technologies-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
GPS, 0211 other engineering and technologies, Construction materials, 02 engineering and technology, Machine learning, computer.software_genre, Field (computer science), Dislocation detection, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Artificial Intelligence, Position (vector), 021105 building & construction, 0202 electrical engineering, electronic engineering, information engineering, Radio-frequency identification, Mathematics, RFID, business.industry, Frame (networking), General Engineering, Function (mathematics), belief functions, Sensors network, Computer Science Applications, Discrete time and continuous time, Global Positioning System, 020201 artificial intelligence & image processing, Artificial intelligence, business, Focus (optics), Algorithm, computer, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

Highlights? The greedy acceptance criterion for the glowworms updating positions is proposed. ? The new formulas for the glowworms movement are proposed. ? Uniform design experiments were investigated the effect of parameters. ? The proposed improvement algorithms were effective than the classical algorithm. Dislocation is defined as the change between discrete sequential locations of critical items in field environments such as large construction projects. Dislocations on large sites of materials and critical items for which discrete time position estimates are available represent critical state changes. The ability to detect dislocations automatically for tens of thousands of items can ultimately improve project performance significantly. Detecting these dislocations in a noisy information environment where low cost radio frequency identification tags are attached to each piece of material, and the material is moved sometimes only a few meters, is the main focus of this study. We propose in this paper a method developed in the frame of belief functions to detect dislocations. The belief function framework is well-suited for such a problem where both uncertainty and imprecision are inherent to the problem. We also show how to deal with the calculations. This method has been implemented in a controlled experimental setting. The results of these experiments show the ability of the proposed method to detect materials dislocation over the site reliably. Broader application of this approach to both animate and inanimate objects is possible.

Published
2012

7. The Impact of Edge Deletions on the Number of Errors in Networks

Author

Christian Glacet, Nicolas Hanusse, David Ilcinkas, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computer science, dynamic graph, Mathematics::History and Overview, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 010501 environmental sciences, Expected value, Network topology, 01 natural sciences, Graph, Combinatorics, shortest path and routing, Mathematics::Logic, 010201 computation theory & mathematics, Algorithm, 0105 earth and related environmental sciences, errors and faults
Abstract

In this paper, we deal with an error model in distributed networks. For a target t, every node is assumed to give an advice, ie. to point to a neighbour that take closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars. More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever l deleted edges are chosen uniformly at random, for any graph with n nodes, m edges and diameter D, we prove that the expected number of liars and distance changes is $O(\frac{\ell^2Dn}{m})$ in the resulting graph. The result is tight for l=1. For some specific topologies, we give more precise bounds.

Published
2011

8. Communication algorithms with advice

Author

Pierre Fraigniaud, Andrzej Pelc, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Computer Networks and Communications, Distributed computing, Message complexity, Network, 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Graph, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Size of advice, Dissemination, Mathematics, Linear number, business.industry, Applied Mathematics, Telecommunications network, Algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Broadcast communication network, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Advice (complexity), Wakeup
Abstract

International audience; We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

Published
2010