1 |
Contribution à la parallélisation automatique : un modèle de processeur à beaucoup de coeurs parallélisant. / Contribution to the automatic parallelization : the model of the manycore parallelizing processorPorada, Katarzyna 14 November 2017 (has links)
Depuis les premiers ordinateurs on est en quête de machines plus rapides, plus puissantes, plus performantes. Après avoir épuisé le filon de l’augmentation de la fréquence, les constructeurs se sont tournés vers les multi-cœurs. Le modèle de calcul actuel repose sur les threads de l'OS qu’on exploite à travers différents langages à constructions parallèles. Cependant, la programmation multithread reste un art délicat car le calcul parallèle découpé en threads souffre d’un grand défaut : il est non déterministe.Pourtant, on peut faire du calcul parallèle déterministe, à condition de remplacer le modèle des threads par un modèle s’appuyant sur l’ordre partiel des dépendances. Dans cette thèse, nous proposons un modèle alternatif d’architecture qui exploite le parallélisme d’instructions (ILP) présent dans les programmes. Nous proposons de nombreuses techniques pour s’affranchir de la plupart des dépendances architecturales et obtenir ainsi un ILP qui croît avec la taille de l’exécution. L’ILP qu’on atteint de cette façon est suffisant pour permettre d’alimenter plusieurs milliers de cœurs. Les dépendances architecturales sérialisantes ayant été supprimées, l’ILP peut être bien mieux exploité que dans les architectures actuelles. Un code VHDL au niveau RTL de l’architecture a été développé pour en mesurer les avantages. Les résultats de synthèse d’un processeur allant de 2 à 64 cœurs montrent que la vitesse du matériel que nous proposons reste constante et que sa surface varie linéairement avec le nombre de cœurs. Cela prouve que le modèle d’interconnexion proposé est extensible. / The pursuit for faster and more powerful machines started from the first computers. After exhausting the increase of the frequency, the manufacturers have turned to another solution and started to introduce multiples cores on a chip. The computational model is today based on the OS threads exploited through different languages offering parallel constructions. However, parallel programming remains an art because the thread management by the operating system is not deterministic.Nonetheless, it is possible to compute in a parallel deterministic way if we replace the thread model by a model built on the partial order of dependencies. In this thesis, we present an alternative architectural model exploiting the Instruction Level Parallelism (ILP) naturally present in applications. We propose many techniques to remove most of the architectural dependencies which leads to an ILP increasing with the execution length. The ILP which is reached this way is enough to allow feeding thousands of cores. Eliminating the architecutral dependencies serializing the run allows to exploit the ILP better than in actual microarchitectures. A VHDL code at the RTL level has been implemented to mesure the benefits of our design. The results of the synthesis of a processeur ranging from 2 to 64 cores are reported. They show that the speed of the proposed material keeps constant and the surface grows linearly with the number of cores : our interconnect solution is scalable.
|
2 |
Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe. / Combinatorial Techniques for Parameterized Algorithms and Kernels, with Applications to Multicut.Daligault, Jean 05 July 2011 (has links)
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.
|
3 |
Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe.Daligault, Jean 05 July 2011 (has links) (PDF)
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.
|
4 |
Construction of algebraic curves with many rational points over finite fields / Construction of algebraic curves with many rational points over finite fieldsDucet, Virgile 23 September 2013 (has links)
L'étude du nombre de points rationnels d'une courbe définie sur un corps fini se divise naturellement en deux cas : lorsque le genre est petit (typiquement g<=50), et lorsqu'il tend vers l'infini. Nous consacrons une partie de cette thèse à chacun de ces cas. Dans la première partie de notre étude nous expliquons comment calculer l'équation de n'importe quel revêtement abélien d'une courbe définie sur un corps fini. Nous utilisons pour cela la théorie explicite du corps de classe fournie par les extensions de Kummer et d'Artin-Schreier-Witt. Nous détaillons également un algorithme pour la recherche de bonnes courbes, dont l'implémentation fournit de nouveaux records de nombre de points sur les corps finis d'ordres 2 et 3. Nous étudions dans la seconde partie une formule de trace d'opérateurs de Hecke sur des formes modulaires quaternioniques, et montrons que les courbes de Shimura associées forment naturellement des suites récursives de courbes asymptotiquement optimales sur une extension quadratique du corps de base. Nous prouvons également qu'alors la contribution essentielle en points rationnels est fournie par les points supersinguliers. / The study of the number of rational points of a curve defined over a finite field naturally falls into two cases: when the genus is small (typically g<=50), and when it tends to infinity. We devote one part of this thesis to each of these cases. In the first part of our study, we explain how to compute the equation of any abelian covering of a curve defined over a finite field. For this we use explicit class field theory provided by Kummer and Artin-Schreier-Witt extensions. We also detail an algorithm for the search of good curves, whose implementation provides new records of number of points over the finite fields of order 2 and 3. In the second part, we study a trace formula of Hecke operators on quaternionic modular forms, and we show that the associated Shimura curves of the form naturally form recursive sequences of asymptotically optimal curves over a quadratic extension of the base field. Moreover, we then prove that the essential contribution to the rational points is provided by supersingular points.
|
5 |
Essays in dynamic panel data models and labor supplyNayihouba, Kolobadia Ada 08 1900 (has links)
Cette thèse est organisée en trois chapitres. Les deux premiers proposent
une approche régularisée pour l’estimation du modèle de données de panel
dynamique : l’estimateur GMM et l’estimateur LIML. Le dernier chapitre de
la thèse est une application de la méthode de régularisation à l’estimation
des élasticités de l’offre de travail en utilisant des modèles de pseudo-données
de panel.
Dans un modèle de panel dynamique, le nombre de conditions de moments
augmente rapidement avec la dimension temporelle du panel conduisant à
une matrice de covariance des instruments de grande dimension. L’inversion
d’une telle matrice pour calculer l’estimateur affecte négativement les propriétés
de l’estimateur en échantillon fini. Comme solution à ce problème,
nous proposons une approche par la régularisation qui consiste à utiliser une
inverse généralisée de la matrice de covariance au lieu de son inverse classique.
Trois techniques de régularisation sont utilisées : celle des composantes
principales, celle de Tikhonov qui est basée sur le Ridge régression (aussi appelée
Bayesian shrinkage) et enfin celle de Landweber Fridman qui est une
méthode itérative. Toutes ces techniques introduisent un paramètre de régularisation
qui est similaire au paramètre de lissage dans les régressions non
paramétriques. Les propriétés en echantillon fini de l’estimateur régularisé
dépend de ce paramètre qui doit être sélectionné parmis plusieurs valeurs
potentielles.
Dans le premier chapitre (co-écrit avec Marine Carrasco), nous proposons
l’estimateur GMM régularisé du modèle de panel dynamique. Sous l’hypothèse
que le nombre d’individus et de périodes du panel tendent vers l’infini,
nous montrons que nos estimateurs sont convergents and assymtotiquement
normaux. Nous dérivons une méthode empirique de sélection du paramètrede régularisation basée sur une expansion de second ordre du l’erreur quadratique
moyenne et nous démontrons l’optimalité de cette procédure de sélection.
Les simulations montrent que la régularisation améliore les propriétés
de l ’estimateur GMM classique. Comme application empirique, nous avons
analysé l’effet du développement financier sur la croissance économique.
Dans le deuxième chapitre (co-écrit avec Marine Carrasco), nous nous intéressons
à l’estimateur LIML régularisé du modèle de données de panel
dynamique. L’estimateur LIML est connu pour avoir de meilleures propriétés
en échantillon fini que l’estimateur GMM mais son utilisation devient
problématique lorsque la dimension temporelle du panel devient large. Nous
dérivons les propriétes assymtotiques de l’estimateur LIML régularisé sous
l’hypothèse que le nombre d’individus et de périodes du panel tendent vers
l’infini. Une procédure empirique de sélection du paramètre de régularisation
est aussi proposée. Les bonnes performances de l’estimateur régularisé par
rapport au LIML classique (non régularisé), au GMM classique ainsi que le
GMM régularisé sont confirmées par des simulations.
Dans le dernier chapitre, je considère l’estimation des élasticités d’offre de travail
des hommes canadiens. L’hétérogéneité inobservée ainsi que les erreurs de
mesures sur les salaires et les revenus sont connues pour engendrer de l’endogéneité
quand on estime les modèles d’offre de travail. Une solution fréquente
à ce problème d’endogéneité consiste à régrouper les données sur la base des
carastéristiques observables et d’ éffectuer les moindres carrées pondérées sur
les moyennes des goupes. Il a été démontré que cet estimateur est équivalent
à l’estimateur des variables instrumentales sur les données individuelles avec
les indicatrices de groupe comme instruments. Donc, en présence d’un grand
nombre de groupe, cet estimateur souffre de biais en échantillon fini similaire
à celui de l’estimateur des variables instrumentales quand le nombre d’instruments
est élevé. Profitant de cette correspondance entre l’estimateur sur
les données groupées et l’estimateur des variables instrumentales sur les données
individuelles, nous proposons une approche régularisée à l’estimation du
modèle. Cette approche conduit à des élasticités substantiellement différentes
de ceux qu’on obtient en utilisant l’estimateur sur données groupées. / This thesis is organized in three chapters. The first two chapters propose
a regularization approach to the estimation of two estimators of the dynamic
panel data model : the Generalized Method of Moment (GMM) estimator
and the Limited Information Maximum Likelihood (LIML) estimator. The
last chapter of the thesis is an application of regularization to the estimation
of labor supply elasticities using pseudo panel data models.
In a dynamic panel data model, the number of moment conditions increases
rapidly with the time dimension, resulting in a large dimensional covariance
matrix of the instruments. Inverting this large dimensional matrix to compute
the estimator leads to poor finite sample properties. To address this
issue, we propose a regularization approach to the estimation of such models
where a generalized inverse of the covariance matrix of the intruments is used
instead of its usual inverse. Three regularization schemes are used : Principal
components, Tikhonov which is based on Ridge regression (also called Bayesian
shrinkage) and finally Landweber Fridman which is an iterative method.
All these methods involve a regularization parameter which is similar to the
smoothing parameter in nonparametric regressions. The finite sample properties
of the regularized estimator depends on this parameter which needs
to be selected between many potential values.
In the first chapter (co-authored with Marine Carrasco), we propose the regularized
GMM estimator of the dynamic panel data models. Under double
asymptotics, we show that our regularized estimators are consistent and
asymptotically normal provided that the regularization parameter goes to
zero slower than the sample size goes to infinity. We derive a data driven
selection of the regularization parameter based on an approximation of the
higher-order Mean Square Error and show its optimality. The simulations confirm that regularization improves the properties of the usual GMM estimator.
As empirical application, we investigate the effect of financial development
on economic growth.
In the second chapter (co-authored with Marine Carrasco), we propose the
regularized LIML estimator of the dynamic panel data model. The LIML
estimator is known to have better small sample properties than the GMM
estimator but its implementation becomes problematic when the time dimension
of the panel becomes large. We derive the asymptotic properties of
the regularized LIML under double asymptotics. A data-driven procedure to
select the parameter of regularization is proposed. The good performances
of the regularized LIML estimator over the usual (not regularized) LIML estimator,
the usual GMM estimator and the regularized GMM estimator are
confirmed by the simulations.
In the last chapter, I consider the estimation of the labor supply elasticities
of Canadian men through a regularization approach. Unobserved heterogeneity
and measurement errors on wage and income variables are known to
cause endogeneity issues in the estimation of labor supply models. A popular
solution to the endogeneity issue is to group data in categories based
on observable characteristics and compute the weighted least squares at the
group level. This grouping estimator has been proved to be equivalent to instrumental
variables (IV) estimator on the individual level data using group
dummies as intruments. Hence, in presence of large number of groups, the
grouping estimator exhibites a small bias similar to the one of the IV estimator
in presence of many instruments. I take advantage of the correspondance
between grouping estimators and the IV estimator to propose a regularization
approach to the estimation of the model. Using this approach leads to
wage elasticities that are substantially different from those obtained through
grouping estimators.
|
Page generated in 0.0425 seconds