• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 101
  • 96
  • 39
  • 1
  • Tagged with
  • 232
  • 232
  • 154
  • 143
  • 119
  • 117
  • 99
  • 99
  • 98
  • 95
  • 94
  • 90
  • 49
  • 46
  • 44
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Exploiting parallel features of modern computer architectures in bioinformatics : applications to genetics, structure comparison and large graph analysis / Exploiter les capacités de calcul parallèle des architectures modernes en bioinformatique

Chapuis, Guillaume 18 December 2013 (has links)
La croissance exponentielle de la génération de données pour la bioinformatique couplée à une stagnation des fréquences d’horloge des processeurs modernes accentuent la nécessité de fournir des implémentation tirant bénéfice des capacités parallèles des ordinateurs modernes. Cette thèse se concentre sur des algorithmes et implementations pour des problèmes de bioinformatique. Plusieurs types de parallélisme sont décrits et exploités. Cette thèse présente des applications en génétique, avec un outil de détection de QTL paralllisé sur GPU, en comparaison de structures de protéines, avec un outil permettant de trouver des régions similaires entre protéines parallélisé sur CPU, ainsi qu’à l’analyse de larges graphes avec une implémentation multi-GPUs d’un nouvel algorithme pour le problème du «All-Pairs Shortest Path». / The exponential growth in bioinformatics data generation and the stagnation of processor frequencies in modern processors stress the need for efficient implementations that fully exploit the parallel capabilities offered by modern computers. This thesis focuses on parallel algorithms and implementations for bioinformatics problems. Various types of parallelism are described and exploited. This thesis presents applications in genetics with a GPU parallel tool for QTL detection, in protein structure comparison with a multicore parallel tool for finding similar regions between proteins, and large graph analysis with a multi-GPU parallel implementation for a novel algorithm for the All-Pairs Shortest Path problem.
2

Exploring the neural codes using parallel hardware / Explorer les codes neuronaux utilisant des machines parallèles

Baladron Pezoa, Javier 07 June 2013 (has links)
L'objectif de cette thèse est de comprendre la dynamique des grandes populations de neurones interconnectées. La méthode utilisée pour atteindre cet objectif est un mélange de modèles mésoscopiques et calculs de haute performance. Le premier permet de réduire la complexité du réseau neuronale et le second de réaliser des simulations à grandes échelles. Dans la première partie de cette thèse une nouvelle approche du champ moyen est utilisée pour étudier numériquement les effets du bruit sur un groupe extrêmement grand de neurones. La même approche a été utilisée pour créer un modèle d' hypercolonne du premier cortex visuel d'où l'unité basique, est des grandes populations de neurones au lieu d'une seule cellule. Les simulations sont réalisées en résolvant un système d'équation différentielle partielle qui décrit l'évolution de la fonction de densité de probabilité du réseau. Dans la deuxième partie de cette thèse est présentée une étude numérique de deux modèles de champs neuronaux du premier cortex visuel. Le principal objectif est de déterminer comment les contours sont sélectionnés dans le cortex visuel. La différence entre les deux modèles est la manière de représenter des préférences d'orientations des neurones. Pour l'un des modèles, l'orientation est une caractéristique de l'équation et la connectivité dépend d'elle. Dans l'autre, il existe une carte d'orientation qui définit une fonction d'entrée. Toutes les simulations sont réalisées sur un cluster de processeurs graphiques. Cette thèse propose des techniques pour simuler rapidement les modèles proposés sur ce type de machine. La vitesse atteinte est équivalente à un cluster standard très grand. / The aim of this thesis is to understand the dynamics of large interconnected populations of neurons. The method we use to reach this objective is a mixture of mesoscopic modeling and high performance computing. The rst allows us to reduce the complexity of the network and the second to perform large scale simulations. In the rst part of this thesis a new mean eld approach for conductance based neurons is used to study numerically the eects of noise on extremely large ensembles of neurons. Also, the same approach is used to create a model of one hypercolumn from the primary visual cortex where the basic computational units are large populations of neurons instead of simple cells. All of these simulations are done by solving a set of partial dierential equations that describe the evolution of the probability density function of the network. In the second part of this thesis a numerical study of two neural eld models of the primary visual cortex is presented. The main focus in both cases is to determine how edge selection and continuation can be computed in the primary visual cortex. The dierence between the two models is in how they represent the orientation preference of neurons, in one this is a feature of the equations and the connectivity depends on it, while in the other there is an underlying map which denes an input function. All the simulations are performed on a Graphic Processing Unit cluster. Thethesis proposes a set of techniques to simulate the models fast enough on this kind of hardware. The speedup obtained is equivalent to that of a huge standard cluster.
3

Ordonnancement efficace d'applications parallèles : les tâches malléables monotones

Mounié, Grégory 26 June 2000 (has links) (PDF)
La répartition des calculs et des données est le problème majeur à résoudre pour réaliser une application parallèle, son efficacité dépendant de la date et du lieu d'exécution des calculs sur l'ensemble des ressources, processeurs et mémoire, de la machine. Nous nous attachons à résoudre ce "problème d'ordonnancement". Nous utilisons pour cela un modèle proposé récemment : les tâches malléables. Après une introduction au domaine du parallélisme, nous présentons les principaux défauts d'autres modèles d'exécution, notamment leur modélisation fine du comportement des échanges de données, ce qui rend leur manipulation complexe. Les problèmes d'ordonnancement qui en résultent nous semblent difficiles à résoudre efficacement. Le modèle des tâches malléables considère une application comme un ensemble de tâches parallèles, chacune étant exécutée simultanément par plusieurs processeurs. La modélisation d'une application reste classique, en graphe de tâches, mais les communications ne sont prises en compte que de manière implicite, dans le temps d'exécution de chaque tâche malléable. Nous pensons que cette approche simplifie le problème d'ordonnancement à la fois théorique et pratique. Dans ce mémoire, nous abordons d'abord l'ordonnancement de tâches malléables indépendantes. Nous présentons quelques travaux déjà connus dont nous analysons les déficiences. Nous proposons un algorithme en deux étagères avec une meilleure garantie de performance de 3/2. Une comparaison en moyenne des différents algorithmes est également présentée. Pour les problèmes incluant des contraintes de précédences, nous présentons d'abord les résultats existants dans des modèles proches avant de proposer une première étude du problème des chaînes de tâches malléables. Enfin, après une introduction au domaine de la simulation adaptative de courants océaniques, l'utilisation pratique du modèle pour l'ordonnancement d'une simulation est également présentée.
4

Artificial intelligence models for large scale buildings energy consumption analysis / Modèles d'intelligence artificielle pour analyse énergétique des bâtiments de la consommation

Zhao, Haixiang 28 September 2011 (has links)
La performance énergétique dans les bâtiments est influencée par de nombreux facteurs, tels que les conditions météorologiques ambiantes, la structure du bâtiment et les caractéristiques, l'occupation et leurs comportements, l'opération de sous-composants de niveau comme le chauffage, de ventilation et de climatisation (CVC). Cette propriété rend complexe la prévision, l'analyse, ou faute de détection / diagnostic de la consommation énergétique du bâtiment est très difficile d'effectuer rapidement et avec précision. Cette thèse se concentre principalement sur la mise à jour des modèles d'intelligence artificielle avec des applications pour résoudre ces problèmes. Tout d'abord, nous passons en revue les modèles récemment développés pour résoudre ces problèmes, y compris des méthodes d'ingénierie détaillée et simplifiée, les méthodes statistiques et les méthodes d'intelligence artificielle. Puis nous simulons des profils de consommation d'énergie pour les bâtiments simples et multiples, et basé sur ces ensembles de données, des modèles de soutien vecteur de la machine sont formés et testés pour faire la prédiction. Les résultats des expériences montrent vaste précision de la prédiction haute et la robustesse de ces modèles. Deuxièmement, déterministe récursif Perceptron (RDP) modèle de réseau neuronal est utilisé pour détecter et diagnostiquer défectueuse consommation d'énergie du bâtiment. La consommation anormale est simulé par l'introduction manuelle d'une dégradation des performances des appareils électriques. Dans l'expérience, le modèle montre la capacité de détection RDP très élevé. Une nouvelle approche est proposée pour diagnostiquer des défauts. Il est basé sur l'évaluation des modèles RDP, dont chacun est capable de détecter une panne de matériel. Troisièmement, nous examinons comment la sélection des sous-ensembles caractéristiques de l'influence la performance du modèle. Les caractéristiques optimales sont choisis en fonction de la faisabilité de l'obtention eux et sur les scores qu'ils fournissent dans l'évaluation de deux méthodes de filtrage. Les résultats expérimentaux confirmer la validité de l'ensemble sélectionné et montrent que la proposé la méthode de sélection fonction peut garantir l'exactitude du modèle et réduit le temps de calcul. Un défi de la consommation énergétique du bâtiment est d'accélérer la prédiction de formation du modèle lorsque les données sont très importantes. Cette thèse propose une mise en œuvre efficace parallèle de Support Vector Machines basée sur la méthode de décomposition pour résoudre de tels problèmes. La parallélisation est réalisée sur le travail le plus fastidieux de formation, c'est à dire de mettre à jour le vecteur gradient de f. Les problèmes intérieurs sont traitées par solveur d'optimisation séquentielle minimale. Le parallélisme sous-jacente est réalisée par la version de mémoire partagée de Map-Reduce paradigme, qui rend le système particulièrement adapté pour être appliqué à des systèmes multi-core et multi-processeurs. Les résultats expérimentaux montrent que notre implémentation offre une augmentation de la vitesse élevée par rapport à libsvm, et il est supérieur à l'état de l'art Pisvm application MPI à la fois la rapidité et l'exigence de stockage. / The energy performance in buildings is influenced by many factors, such as ambient weather conditions, building structure and characteristics, occupancy and their behaviors, the operation of sub-level components like Heating, Ventilation and Air-Conditioning (HVAC) system. This complex property makes the prediction, analysis, or fault detection/diagnosis of building energy consumption very difficult to accurately and quickly perform. This thesis mainly focuses on up-to-date artificial intelligence models with the applications to solve these problems. First, we review recently developed models for solving these problems, including detailed and simplified engineering methods, statistical methods and artificial intelligence methods. Then we simulate energy consumption profiles for single and multiple buildings, and based on these datasets, support vector machine models are trained and tested to do the prediction. The results from extensive experiments demonstrate high prediction accuracy and robustness of these models. Second, Recursive Deterministic Perceptron (RDP) neural network model is used to detect and diagnose faulty building energy consumption. The abnormal consumption is simulated by manually introducing performance degradation to electric devices. In the experiment, RDP model shows very high detection ability. A new approach is proposed to diagnose faults. It is based on the evaluation of RDP models, each of which is able to detect an equipment fault.Third, we investigate how the selection of subsets of features influences the model performance. The optimal features are selected based on the feasibility of obtaining them and on the scores they provide under the evaluation of two filter methods. Experimental results confirm the validity of the selected subset and show that the proposed feature selection method can guarantee the model accuracy and reduces the computational time.One challenge of predicting building energy consumption is to accelerate model training when the dataset is very large. This thesis proposes an efficient parallel implementation of support vector machines based on decomposition method for solving such problems. The parallelization is performed on the most time-consuming work of training, i.e., to update the gradient vector f. The inner problems are dealt by sequential minimal optimization solver. The underlying parallelism is conducted by the shared memory version of Map-Reduce paradigm, making the system particularly suitable to be applied to multi-core and multiprocessor systems. Experimental results show that our implementation offers a high speed increase compared to Libsvm, and it is superior to the state-of-the-art MPI implementation Pisvm in both speed and storage requirement.
5

Calcul à l'echelle méso avec interface non locale des composites stratifiés / Meso scale with non local interface simulation of stratified composite

Bordeu Weldt, Felipe Eduardo 06 January 2012 (has links)
L'industrie utilise de plus en plus les matériaux composites stratifiés à matrice organique (CMO) pour remplacer les alliages métalliques légers. Avec un rapport résistance/masse supérieur aux alliages métalliques, ces matériaux constituent une véritable alternative pour diminuer le poids des structures. Cependant, la certification des structures en composite est une procédure lourde et complexe. Le Virtual Testing consiste à remplacer une grande partie des essais réels par des simulations numériques en vue de diminuer la quantité d'essais physiques nécessaires pour la certification. Toutefois, les modèles ainsi que les méthodes de calcul utilisés pour les simulations doivent avoir la confiance des autorités de contrôle. On ce concentre ici sur le Méso-modèle Amélioré d'Endommagement des Composites Stratifiés qui, depuis un vingtaine d'années, a démontré être un modèle capable de prendre en compte la plupart de mécanismes de dégradation d'une structure composite. Ce modèle, non linéaire, non local et d'évolution, est défini à l'échelle du pli. La taille des problèmes résultants de la simulation de ce type de modèle est considérable. Dans ces travaux, un grand intérêt a été porté au traitement numérique du modèle. Dans un premier temps, l'intégration du modèle dans un code de calcul a permis d'y apporter des améliorations. En ce qui concerne la méthode de résolution, une méthode de décomposition de domaine permet l'utilisation du modèle pour la simulation de structures de taille moyenne. L'approche proposée permet de surmonter les difficultés liées à l'utilisation d'un modèle non local et non linéaire au sein d'une méthode de décomposition de domaine. / The industry uses more and more organic matrix composite materials to replace the light metallic alloys. With a strenght/mass ratio superior to the metallic alloys, these materials constitute a real alternative to decrease the weight of the structures. However, the certification of composite structures is a heavy and complex procedure. Virtual Testing consists in replacing a big part of the real essays by numeric simulations to decrease the quantity of physical essays necessary for the certification. However, the models as well as the numerical methods used for the simulations have to be trusted by the certification authorities. Here we focus on the Enhanced Damage Mesomodel which, for twenty years, has demonstrated to be a model capable of taking into account most of the degradation mechanisms of a composite structure. This non linear and non local model is defined at the composite layer scale. The size of the problems generated by a simulation with this type of model is considerable. In this work, special emphasis was put on the numerical treatment of the model. At first, the integration of the model in a simulation code allowed us to improve it. With regards to the resolution method, a domain decomposition method allows the use of the model for the simulation of intermediate-sized structures. The proposed approach allows to surmount the difficulties linked to the use of a not local and not linear model within a method of decomposition of domain.
6

Simulation des réseaux à grande échelle sur les architectures de calculs hétérogènes / Large-scale network simulation over heterogeneous computing architecture

Ben Romdhanne, Bilel 16 December 2013 (has links)
La simulation est une étape primordiale dans l'évolution des systèmes en réseaux. L’évolutivité et l’efficacité des outils de simulation est une clef principale de l’objectivité des résultats obtenue, étant donné la complexité croissante des nouveaux des réseaux sans-fils. La simulation a évènement discret est parfaitement adéquate au passage à l'échelle, cependant les architectures logiciel existantes ne profitent pas des avancées récente du matériel informatique comme les processeurs parallèle et les coprocesseurs graphique. Dans ce contexte, l'objectif de cette thèse est de proposer des mécanismes d'optimisation qui permettent de surpasser les limitations des approches actuelles en combinant l’utilisation des ressources de calcules hétérogène. Pour répondre à la problématique de l’efficacité, nous proposons de changer la représentation d'événement, d'une représentation bijective (évènement-descripteur) à une représentation injective (groupe d'évènements-descripteur). Cette approche permet de réduire la complexité de l'ordonnancement d'une part et de maximiser la capacité d'exécuter massivement des évènements en parallèle d'autre part. Dans ce sens, nous proposons une approche d'ordonnancement d'évènements hybride qui se base sur un enrichissement du descripteur pour maximiser le degré de parallélisme en combinons la capacité de calcule du CPU et du GPU dans une même simulation. Les résultats comparatives montre un gain en terme de temps de simulation de l’ordre de 100x en comparaison avec une exécution équivalente sur CPU uniquement. Pour répondre à la problématique d’évolutivité du système, nous proposons une nouvelle architecture distribuée basée sur trois acteurs. / The simulation is a primary step on the evaluation process of modern networked systems. The scalability and efficiency of such a tool in view of increasing complexity of the emerging networks is a key to derive valuable results. The discrete event simulation is recognized as the most scalable model that copes with both parallel and distributed architecture. Nevertheless, the recent hardware provides new heterogeneous computing resources that can be exploited in parallel.The main scope of this thesis is to provide a new mechanisms and optimizations that enable efficient and scalable parallel simulation using heterogeneous computing node architecture including multicore CPU and GPU. To address the efficiency, we propose to describe the events that only differs in their data as a single entry to reduce the event management cost. At the run time, the proposed hybrid scheduler will dispatch and inject the events on the most appropriate computing target based on the event descriptor and the current load obtained through a feedback mechanisms such that the hardware usage rate is maximized. Results have shown a significant gain of 100 times compared to traditional CPU based approaches. In order to increase the scalability of the system, we propose a new simulation model, denoted as general purpose coordinator-master-worker, to address jointly the challenge of distributed and parallel simulation at different levels. The performance of a distributed simulation that relies on the GP-CMW architecture tends toward the maximal theoretical efficiency in a homogeneous deployment. The scalability of such a simulation model is validated on the largest European GPU-based supercomputer
7

Simulation de la formabilité des alliages d'aluminium AA5754 et AA6063

Eljaafari, Samira January 2008 (has links)
Les besoins de réduction du poids se sont concrètement traduits par l'introduction de nouvelles nuances plus légères dans les structures automobiles. Ainsi, des alliages d'aluminium ont commencé à être intégrés dans les pièces de structure de plusieurs véhicules. La faible masse volumique des alliages d'aluminium (2,7g/cm 3 ) permet d'alléger le poids du véhicule qui entraîne une diminution de la consommation de carburant et, donc, des émissions de gaz à effet de serre. La striction et la rupture sont les principaux modes de défaillance qui entrainent le rebut systématique des pièces. C'est pourquoi, améliorer la prédiction d'apparition de ces défauts lors de la simulation va dans le sens d'une meilleure maitrise du procédé. Dans le cadre de ce travail doctoral, deux modèles sont développés pour simuler le comportement à grandes déformations d'alliages d'aluminium : un modèle polycristallin de type Taylor et un modèle à un ou plusieurs éléments finis par grain.Les diagrammes limites de formage (DLF) pour les deux alliages d'aluminium AA5754 et AA6063 ont été simulés numériquement en utilisant une formulation par éléments finis pour les polycristaux basée sur l'hypothèse de Taylor.Les DLF conventionnels et de l'hydroformage ont été traces. L'effet des chemins de déformation sur la formabilité des alliages d'aluminium a aussi été étudié. Finalement, des simulations numériques avec les données de diffraction des électrons rétrodiffusés (EBSD) pour l'alliage d'aluminium AA5754 ont été effectuées en utilisant le modèle à un ou plusieurs éléments par grain. Ces simulations sont exécutées avec différents modèles du durcissement (Asaro, Bassani et puissance).
8

Implémentation des filtres non-linéaires de rang sur des architectures universelles et reconfigurables

Milojevic, Dragomir 08 November 2004 (has links)
Les filtres non-linéaires de rang sont souvent utilisés dans le but de rehausser la qualité d'une image numérique. Leur application permet de faciliter l'interprétation visuelle et la compréhension du contenu des images que ce soit pour un opérateur humain ou pour un traitement automatique ultérieur. Dans le pipeline d'une chaîne habituelle de traitement des images, ces filtres sont appliqués généralement dans la phase de pré-traitement, juste après l'acquisition et avant le traitement et l'analyse d'image proprement dit. Les filtres de rang sont considérés comme un important goulot d'étranglement dans la chaîne de traitement, à cause du tri des pixels dans chaque voisinage, à effectuer pour tout pixel de l'image. Les temps de calcul augmentent de façon significative avec la taille de l'image à traiter, la taille du voisinage considéré et lorsque le rang approche la médiane. Cette thèse propose deux solutions à l'accélération du temps de traitement des filtres de rang. La première solution vise l'exploitation des différents niveaux de parallélisme des ordinateurs personnels d'aujourd'hui, notamment le parallélisme de données et le parallélisme inter-processeurs. Une telle approche présente un facteur d'accélération de l'ordre de 10 par rapport à une approche classique qui fait abstraction du matériel grâce aux compilateurs des langages évolués. Si le débit résultant des pixels traités, de l'ordre d'une dizaine de millions de pixels par seconde, permet de travailler en temps réel avec des applications vidéo, peu de temps reste pour d'autres traitements dans la chaîne. La deuxième solution proposée est basée sur le concept de calcul reconfigurable et réalisée à l'aide des circuits FPGA (Field Programmable Gate Array). Le système décrit combine les algorithmes de type bit-série et la haute densité des circuits FPGA actuels. Il en résulte un système de traitement hautement parallèle, impliquant des centaines d'unités de traitement par circuit FPGA et permet d'arriver à un facteur d'accélération supplémentaire de l'ordre de 10 par rapport à la première solution présentée. Un tel système, inséré entre une source d'image numérique et un système hôte, effectue le calcul des filtres de rang avec un débit de l'ordre de centaine de millions de pixels par seconde.
9

Le calcul parallèle des plus courts chemins temporels

Pépin, Jean-Nicolas January 2003 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
10

Contributions à l'algèbre linéaire exacte sur corps finis et au chiffrement homomorphe / Contributions in sparse linear algebra on finite fields and homomorphic encryption

Vialla, Bastien 14 December 2015 (has links)
Cette thèse est composée de deux axes principaux, le premier portant sur le chiffrement homomorphe et le second sur l’algèbre linéaire creuse sur corps finis. Avec l’essor des technologies de communication et en particulier d’internet, de nouveaux protocoles de chiffrement sont développés. En particulier, le besoin de systèmes de chiffrement permettant de manipuler les données chiffrées tout en assurant leur sécurité. C’est dans ce contexte que des systèmes de chiffrement homomorphe sont développés, ces protocoles permettent d’effectuer des calculs avec des données chiffrées. La sécurité de ce type système repose sur l’ajout de bruit aux messages à chiffrer. Ce bruit augmente avec chaque opération effectuée, mais il ne doit pas dépasser un certain seuil. Pour contourner ce problème, une technique nommée bootstrapping est utilisée permettant de réduire le bruit d’un chiffré. Les bootstrappings sont le goulot d’étranglement lors des calculs sur des données chiffrées, il est important d’en faire le moins possible. Or la quantité de bootstrappings à faire est déterminée par la nature des calculs à effectuer ainsi que du protocole de chiffrement utilisé.C’est dans ce contexte que notre travail intervient, nous proposons une méthode effective pour réduire le nombre bootstrappings basé sur la programmation linéaire en nombre entier. Cette méthode s’adapte à un grand nombre de protocoles de chiffrement. De plus, nous effectuons une analyse de la complexité de ce problème en montrant qu’il est APX-complet et nous fournissons un algorithme d’approximation.La résolution de système linéaire sur corps finis est une brique de calcul essentielle dans de nombreux problèmes de calcul formel. En particulier, beaucoup de problèmes produisent des matrices comprenant un grand nombre de zéros, on dit qu’elles sont creuses. Les meilleurs algorithmes permettant de résoudre ce type de système linéaire creux sont des algorithmes dits itératifs. L’opération fondamentale de ces algorithmes itératifs est la multiplication de la matrice par un vecteur ou une matrice dense. Afin d’obtenir les meilleures performances, il est important de tenir compte des propriétés (SIMD, multicoeurs, hiérarchie des caches ....) des processus modernes .C’est dans ce contexte que notre travail intervient, nous étudions la meilleure façon d’implanter efficacement cette opération sur les processeurs récents.Nous proposons un nouveau format permettant de tenir compte du grand nombre de +- 1 présents dans une matrice.Nous proposons une implantation parallèle basée sur le paradigme du vol de tâche offrant un meilleur passage à l’échelle que le parallélisme par threads.Nous montrons comment exploiter au mieux les instructions SIMD des processeurs dans les différentes opérations.Finalement, nous proposons une méthode efficace permettant d’effectuer cette opération lorsque le corps finis est multiprécision (les éléments sont stockés sur plusieurs mots machine) en ayant recours au système de représentation RNS. / This thesis is composed of two independent parts.The first one is related to homomorphic encryption and the second part deal with sparse linear algebra on finite fields.Homomorphic encryption extends traditional encryption in the sense that it becomes feasible to perform operations on ciphertexts, without the knowledge of the secret decryption key. As such, it enables someone to delegate heavy computations on his sensitive data to an untrusted third party, in a secure way. More precisely, with such a system, one user can encrypt his sensitive data such that the third party can evaluate a function on the encrypted data, without learning any information on the underlying plain data. Getting back the encrypted result, the user can use his secret key to decrypt it and obtain, in clear, the result of the evaluation of the function on his sensitive plain data. For a cloud user, the applications are numerous, and reconcile both a rich user experience and a strong privacy protection.The first fully homomorphic encryption (FHE) scheme, able to handle an arbitrary number of additions and multiplications on ciphertexts, has been proposed by Gentry in 2009.In homomorphic encryption schemes, the executed function is typically represented as an arithmetic circuit. In practice, any circuit can be described as a set of successive operation gates, each one being either a sum or a product performed over some ring.In Gentry’s construction, based on lattices, each ciphertext is associated with some noise, which grows at each operation (addition or multiplication) done throughout the evaluation of the function. When this noise reaches a certain limit, decryption is not possible anymore.To overcome this limitation, closely related to the number of operations that the HE.Eval procedure can handle, Gentry proposed in a technique of noise refreshment called“bootstrapping”.The main idea behind this bootstrapping procedure is to homomorphically run the decryptionprocedure of the scheme on the ciphertext, using an encrypted version of the secret key. In this context, our contribution is twofold. We first prove that the lmax-minimizing bootstrapping problem is APX-complete and NP-complete for lmax ≥ 3. We then propose a new method to determine the minimal number of bootstrappings needed for a given FHE scheme and a given circuit.We use linear programming to find the best outcome for our problem. The main advantage of our method over the previous one is that it is highly flexible and can be adapted for numerous types of homomorphic encryption schemes and circuits.Computing a kernel element of a matrix is a fundamental kernel in many computer algebra and cryptography algorithms. Especially, many applications produces matrices with many matrix elements equals to 0.Those matrices are named sparse matrices. Sparse linear algebra is fundamentally relying on iterative approaches such as Wiedemann or Lanczos. The main idea is to replace the direct manipulation of a sparse matrix with its Krylov subspace. In such approach, the cost is therefore dominated by the computation of the Krylov subspace, which is done by successive product of a matrix by a vector or a dense matrix.Modern processor unit characteristics (SIMD, multicores, caches hierarchy, ...) greatly influence algorithm design.In this context our work deal with the best approach to design efficient implementation of sparse matrix vector product for modern processors.We propose a new sparse matrix format dealing with the many +-1 matrix elements to improve performance.We propose a parallel implementation based on the work stealing paradigm that provide a good scaling on multicores architectures.We study the impact of SIMD instructions on sparse matrix operations.Finally, we provide a modular arithmetic implementation based on residue number system to deal with sparse matrix vector product over multiprecision finite fields.

Page generated in 0.0814 seconds