The existence of distributed real-time systems calls for protocols for high accuracy time synchronization between devices. One such protocol, the Precision Time Protocol (PTP) reaches sub microsecond synchronization precision. PTP can be implemented both in hardware and software. This study aimed to analyze how system stress could affect the accuracy and precision of software implemented PTP between two devices. This was done using two Intel Galileo Generation 2 running Linux systems. Software was used to simulate CPU, I/O, network, and OS usage. Data was extracted from software logs and summarized in charts and then analyzed. The results showed that PTP synchronization accuracy and precision does suffer under certain types of system load, most notably under heavy I/O load. However the results might not be applicable to real-world scenario due to limitations in hardware and the synthetic stress tests do not correspond to real-world usage. Further research is required to analyze why and how different types of system load affects PTPs accuracy and precision. / Förekomsten av distribuerade realtidssystem kräver protokoll för noggrann tidssynkronisering mellan enheter. Ett sådant protokoll, Precision Time Protocol (PTP), kan uppnå en precision på under mikrosekunden under synkronisering. PTP kan implementeras i både hårdvara och mjukvara. Den här rapporten fokuserar på att analysera hur systembelastning kan påverka precision och noggrannheten hos mjukvaruimplementerad PTP mellan två enheter. Testen utfördes på två stycken Intel Galileo Generation 2 kö- randes Linux. Mjukvara användes sedan för att simulera belastning på olika system såsom CPU, I/O, nätverk och på operativsystemet. Data extraherades ifrån loggar från mjukvaran, vilken sammanfattades i grafer för att sedan analyseras. Resultaten visade att precisionen och noggrannheten hos PTP försämras under vissa typer av systembelastningar, mest märkbart under tung I/O belastning. Resultaten är dock potentiellt inte applicerbara på verklighetscenarion på grund av begränsingar i hårdvaran samt att syntetiska stresstest inte motsvarar normal belastning. Ytterligare forskning krävs för att analysera hur och varför olika typer av systembelastning påverkar PTPs precision och noggrannhet.

Les horloges atomiques miniatures présentent des stabilités de fréquence inégalées avec des volumes de quelquescentimètres cubes et des consommations inférieures à 100mW.Dans cette thèse, les paramètres optimaux concernant la conception et la fabrication des cellules à vapeur decésium, un des composant clés de ce type d’horloges, sont définis. Ainsi, les performances de plusieurs cellulesont été caractérisées en condition d’horloge à court et long terme. En parallèle, des solutions sont proposéespour pallier à certaines limitations telles que la plage de température opérationnelle, le coût de fabrication dudispositif et la facilité d’assemblage du module physique.Un nouveau mélange de gaz tampon composé de néon et d’hélium peut étendre la plage de fonctionnementau-dessus de 80 C, en adéquation avec les besoins industriels. A l’inverse des gaz tampon usuels, ce mélangeest compatible avec les dispensers de césium solides, dont la fiabilité est établie.Outre les gaz tampon, les revêtements permettent également de limiter la relaxation induite par les parois dela cellule. Ici, des revêtements d’octadécyltrichlorosilane sont étudiés. Un effet anti-relaxant a été observé dansdes cellules centimétriques et un procédé a été développé pour revêtir des cellules micro-fabriquées.D’autres sources de césium sont présentées pour s’affranchir des inconvénients propres aux dispensers solides.Un dispenser sous forme de pâte, qui peut être déposée collectivement, a été étudié et montre des densitésatomiques stables jusqu’à présent. Un concept de vannes hermétiques micro-fabriquées a été proposé poursceller hermétiquement et séparer des cellules d’un réservoir de césium commun.Les premières étapes vers un module physique micro-fabriqué sont ensuite présentées. En particulier, un designoriginal de cellule combinant des réseaux de diffraction à une cavité en silicium formée par gravure anisotropea été caractérisé et a montré des contrastes CPT remarquables malgré un volume de cavité réduit, ce qui permettraitde réaliser un module physique particulièrement compact. Enfin, des cellules intégrant des résistanceschauffantes et thermométriques ont été fabriquées et leur compatibilité vis-à-vis du champ magnétique généréa été caractérisée dans un prototype de module physique compact. / Chip-scale atomic clocks (CSACs) provide unprecedented frequency stability within volumes down to a fewcubic centimeters and power consumptions as low as 100mW.In this work, we determine the optimal parameters regarding the design and the fabrication of cesium vaporcells, one of the key components of a CSAC. For this purpose, cells were characterized on both short and longtermperformances in clock setups. In addition, we propose solutions to overcome present limitations includingthe operating temperature range, the device microfabrication cost and the ease of integration of the physicspackage.A novel mixture of buffer-gas composed of neon and helium was found to potentially extend the operating rangeof the device above 80 C, meeting the industrial requirements. Unlike the well-known buffer gas compositions,this mixture is compatible with solid cesium dispensers whose reliability is established. As an alternativeto buffer gases, wall coatings are known to limit the relaxation induced by sidewalls. Here, we investigatedoctadecyltrichlorosilane (OTS) coatings. An anti-relaxation effect has been observed in centimeter-scale cellsand a process was developed to coat microfabricated cells.Other cesium sources have been investigated to overcome the drawbacks imposed by solid cesium dispensers. Apaste-like dispenser, which can be deposited collectively, was explored and has shown stable atomic densities sofar. Single-use zero-leak micro valves were also proposed to hermetically seal and detach cells from a commoncesium reservoir.Eventually, the first steps toward a microfabricated physics package were made. In particular, an originalcell design combining diffraction gratings with an anisotropically etched single-crystalline silicon sidewalls wascharacterized and exhibited remarkable CPT contrasts despite a reduced cavity volume, which could lead to amore compact physics package. Finally, cells with integrated heating and temperature sensing resistors werefabricated and their magnetic field compliance was characterized in a compact physics package prototype.

Ce travail traite de la modélisation de systèmes complexes constitués de plusieurs composants impliquant des domaines techniques différents. Il se place dans le contexte de la modélisation hétérogène hiérarchique, selon l’approche à base de modèles de calcul. Chaque composant faisant appel à un domaine technique particulier, son comportement peut être modélisé selon un paradigme de modélisation approprié, avec une sémantique différente de celle des autres composants. La modélisation du système global, qui intègre les modèles hétérogènes de ces composants, nécessite donc une adaptation sémantique permettant l’échange entre les divers sous-modèles.Ce travail propose une approche de modélisation de l’adaptation sémantique où les sémantiques du temps et du contrôle sont explicitement spécifiées par le concepteur en définissant des relations sur les occurrences d’évènements d’une part et sur les étiquettes temporelles de ces occurrences d’autre part. Cette approche est intégrée dans la plateforme ModHel’X et testée sur un cas d’étude : un modèle de lève-vitre électrique. / This work takes place in the context of hierarchical heterogeneous modeling using the model of computation approach in order to model complex systems which includes several components from different technical fields.Each of these components is usually designed according to a modeling paradigm that suits the technical domain and is based on specific semantics. Therefore, the overall system, which integrates the heterogeneous models of the components, requires semantic adaptation to ensure proper communication between its various sub-models.In this context, the aim of this thesis is to propose a new approach of semantic adaptation modeling where the semantic adaptation of time and control is specified by defining relationships between the occurrences of events as well as the time tags of these occurrences. This approach was integrated into the ModHel’X platform and tested on the case study of a power window system.

O surgimento e a evolução da vida na terra foram possíveis graças ao desenvolvimento de mecanismos temporais precisos capazes de ajustar os processos fisiológicos que ocorriam no interior do organismo com os ciclos ambientais, promovendo assim, ganhos na capacidade adaptativa e reprodutiva dos indivíduos. Neste contexto, luz e temperatura são as duas pistas temporais mais relevantes para resetar o relógio endógeno e, aparentemente, esses dois zeitgebers trabalham juntos para manter os ritmos circadianos. Uma ampla gama de fotorreceptores e fotopigmentos evoluiu no sentido de perceber com alta sensibilidade a informação fótica fornecida pelo ambiente e, recentemente, foi demonstrado que a detecção de temperatura também pode ser exercida pelos fotopigmentos rodopsina e melanopsina, sendo mediada por canais TRP (Shen et al., 2011). Consideramos as células B16-F10 Per1::Luc como um modelo promissor para o estudo de luz e temperatura em relógios periféricos, uma vez que essa linhagem expressa os dois fotopigmentos apontados com função de termorreceptores em Drosophila. Nossos estudos nos permitiram verificar que a luz não atua como um agente sincronizador nessas células, que se mantiveram em livre curso mesmo após um pulso de 10 min de luz azul (650 lux). Por outro lado, um pulso de temperatura de 2,5º C acima da temperatura de manutenção por 1h atuou ajustando a expressão do gene Per1, imprimindo um ritmo circadiano, diferentemente do observado no controle. Com base nessas informações, hipotetizamos que a informação de luz, percebida via melanopsina na retina de mamíferos, levaria a regulação da temperatura circadiana pelo NSQ, e a temperatura corporal, por sua vez, poderia atuar como uma pista interna para a sincronização dos tecidos periféricos, tendo os canais TRP como mediadores. Para responder esta questão, utilizamos camundongos WT e TrpV1 KO submetidos a diferentes protocolos de luz e avaliamos a expressão de genes do relógio Per1, Per2, Clock e Bmal1 e dos canais TrpV1 e TrpA1 em tecidos periféricos. Identificamos que a glândula suprarrenal, fígado e tecido adiposo marrom possuem uma maquinaria do relógio tipicamente ativa e acreditamos que a oscilação dos genes de relógio observada nesses tecidos é expressiva. Interessantemente, vimos também que o TrpV1, além de ser expresso nos tecidos analisados em animais WT, apresenta uma transcrição rítmica no fígado e tecido adiposo marrom de animais em LD, corroborando nossa hipótese de que canais TRP atuam como mediadores da informação de luz aos tecidos periféricos. Dadas as diferenças encontradas entre os animais WT e TrpV1 KO, sugerimos que a presença do canal TRPV1 pode ser essencial, embora seu grau de envolvimento varie de acordo com o tecido. No que diz respeito ao canal TRPA1, encontramos dois resultados que merecem ser destacados. Primeiramente, identificamos no fígado de camundongos TrpV1 KO mantidos em LD uma provável compensação da expressão de TrpA1 na ausência de TrpV1 e, curiosamente, que o tecido adiposo marrom não expressa o canal TrpA1. Considerando os resultados deste trabalho sobre o envolvimento dos canais TRP em resposta à luz e temperatura, acreditamos ter fortalecido nossa hipótese inicial, principalmente após demonstrarmos o papel do canal TRPV1 e que tecidos periféricos são sincronizados por alterações de temperatura. / The life emergence and evolution on Earth were made possible by the development of precise temporal mechanisms able to adjust the physiological processes within an organism with environmental cycles, thus promoting gains in the adaptive and reproductive capacity of the individuals. In this context, light and temperature are the two most relevant time cues to reset the endogenous clock; apparently these two zeitgebers work together to keep the circadian rhythms. A wide variety of photoreceptors and photopigments evolved in order to precisely perceive the photic information provided by the environment, and recently it has been shown that the temperature detection can also be exerted by the photopigments rhodopsin and melanopsin, being mediated by TRP channels (Shen et al., 2011). We have identified B16-F10 Per1::Luc cells as a promising model for the study of light and temperature effects on peripheral clocks, since this cell line expresses both photopigments pointed as thermoreceptors in Drosophila. Our studies allowed us to demonstrate that light does not act as a synchronizing agent on those cells, which remained in free running after a 10 min pulse of blue light (650 lux). On the other hand, a temperature pulse of 2.5º C above the maintenance temperature, for 1h, adjusted Per1 gene expression, imprinting a circadian rhythm, which was not observed in the control. Based on this information, we hypothesized that the light perceived via melanopsin by the mammalian retina would lead to the regulation of the circadian temperature by the SCN, and the body temperature, in turn, could act as an inner cue for the synchronization of the peripheral tissues, having the TRP channels as mediators. To answer this question, we have used WT and TrpV1 KO mice under different light protocols and evaluated the expression of clock genes Per1, Per2, Clock and Bmal1 and TrpV1 and TrpA1 channels in peripheral tissues. We found that the adrenal gland, liver and brown adipose tissue have a typically active clock machinery, and the oscillation of clock genes observed in these tissues is significant. Interestingly, we observed that TrpV1 is expressed in those tissues, and presents a rhythmic transcription in the liver and brown adipose tissue of LD maintained animals, confirming our hypothesis that TRP channels act as mediators of light information to peripheral tissues. In face of the differences between WT and trpV1 KO animals, we suggest that the presence of the TRPV1 channel may be essential, although its degree of involvement may vary according to the tissue. In terms of TRPA1 channel, we found two results that deserve to be highlighted. Firstly, we identified in the liver of TrpV1 KO mice maintained in LD a presumable compensation of TrpA1 expression in the absence of TrpV1 and, interestingly, the brown adipose tissue does not express TrpA1 channel. Considering the findings of this study on the participation of TRP channels in responses to light and temperature, we believe we have strengthened our initial hypothesis, especially after we have demonstrated the role of TRPV1 channel, and that peripheral tissues may be synchronized by temperature changes.

The Forgiveness Project includes a critical introduction that defines the author’s approach to the short-short form as well as an explanation of how historiographical metafiction can work to memorialize. The first section contains primarily short-short stories that address the themes of motherhood, small tyrannies, happy liars, caregiving and the clichés of grief. A collection of linked short stories follows, revolving around elusive forgiveness. On the night of July 17, 1977, Juanita Lee, a bridge tender in South Florida, was abducted by two men and executed in the Everglades to silence her opposition to the demolition of an Intracoastal Waterway bridge. Twenty-two years later her daughter, Jill, now a Washington D.C. lobbyist who views the world through the cynical lens of her life’s work, is confronted with a plea for forgiveness via an organization called “The Forgiveness Project,” representing one of her mother’s killers.

Nous présentons deux contributions dans le domaine de la programmation parallèle. La première est théorique : nous introduisons l’analyse SIPS, une approche nouvelle pour dénombrer le nombre d’opérations de synchronisation durant l’exécution d’un algorithme parallèle ordonnancé par vol de travail. Basée sur le concept d’horloges logiques, elle nous permet : d’une part de donner de nouvelles majorations de coût en moyenne; d’autre part de concevoir des programmes parallèles plus efficaces par adaptation dynamique de la granularité. La seconde contribution est pragmatique : nous présentons une parallélisation générique d’algorithmes pour la génération déterministe de nombres pseudo-aléatoires, indépendamment du nombre de processus concurrents lors de l’exécution. Alternative à l’utilisation d’un générateur pseudo-aléatoire séquentiel par processus, nous introduisons une API générique, appelée Par-R qui est conçue et analysée grâce à SIPS. Sa caractéristique principale est d’exploiter un générateur séquentiel qui peut “sauter” directement d’un nombre à un autre situé à une distance arbitraire dans la séquence pseudo-aléatoire. Grâce à l’analyse SIPS, nous montrons qu’en moyenne, lors d’une exécution par vol de travail d’un programme très parallèle (dont la profondeur ou chemin critique est très petite devant le travail ou nombre d’opérations), ces opérations de saut sont rares. Par-R est comparé au générateur pseudo-aléatoire DotMix écrit pour Cilk Plus, une extension de C/C++ pour la programmation parallèle par vol de travail. Le surcout théorique de Par-R se compare favorablement au surcoput de DotMix, ce qui apparait aussi expériemntalement. De plus, étant générique, Par-R est indépendant du générateur séquentiel sous-jacent. / Nós apresentamos duas contribuições para a área de programação paralela. A primeira contribuição é teórica: nós introduzimos a análise SIPS, uma nova abordagem para a estimar o número de sincronizações realizadas durante a execução de um algoritmo paralelo. SIPS generaliza o conceito de relógios lógicos para contar o número de sincronizações realizadas por um algoritmo paralelo e é capaz de calcular limites do pior caso mesmo na presença de execuções paralelas não-determinísticas, as quais não são geralmente cobertas por análises no estado-da-arte. Nossa análise nos permite estimar novos limites de pior caso para computações escalonadas pelo popular algoritmo de roubo de tarefas e também projetar programas paralelos e adaptáveis que são mais eficientes. A segunda contribuição é pragmática: nós apresentamos uma estratégia de paralelização eficiente para a geração de números pseudoaleatórios. Como uma alternativa para implementações fixas de componentes de geração aleatória nós introduzimos uma API chamada Par-R, projetada e analisada utilizando-se SIPS. Sua principal idea é o uso da capacidade de um gerador sequencial R de realizar um “pulo” eficiente dentro do fluxo de números gerados; nós os associamos a operações realizadas pelo escalonador por roubo de tarefas, o qual nossa análise baseada em SIPS demonstra ocorrer raramente em média. Par-R é comparado com o gerador paralelo de números pseudoaleatórios DotMix, escrito para a plataforma de multithreading dinâmico Cilk Plus. A latência de Par-R tem comparação favorável à latência do DotMix, o que é confirmado experimentalmente, mas não requer o uso subjacente fixado de um dado gerador aleatório. / We present two contributions to the field of parallel programming. The first contribution is theoretical: we introduce SIPS analysis, a novel approach to estimate the number of synchronizations performed during the execution of a parallel algorithm. Based on the concept of logical clocks, it allows us: on one hand, to deliver new bounds for the number of synchronizations, in expectation; on the other hand, to design more efficient parallel programs by dynamic adaptation of the granularity. The second contribution is pragmatic: we present an efficient parallelization strategy for pseudorandom number generation, independent of the number of concurrent processes participating in a computation. As an alternative to the use of one sequential generator per process, we introduce a generic API called Par-R, which is designed and analyzed using SIPS. Its main characteristic is the use of a sequential generator that can perform a “jump-ahead” directly from one number to another on an arbitrary distance within the pseudorandom sequence. Thanks to SIPS, we show that, in expectation, within an execution scheduled by work stealing of a “very parallel” program (whose depth or critical path is subtle when compared to the work or number of operations), these operations are rare. Par-R is compared with the parallel pseudorandom number generator DotMix, written for the Cilk Plus dynamic multithreading platform. The theoretical overhead of Par-R compares favorably to DotMix’s overhead, what is confirmed experimentally, while not requiring a fixed generator underneath.

Mes travaux de thèse ont pour finalité la réalisation d’un transfert de temps intercontinentald’une stabilité meilleure que 2 ns sur 10 000 s, entre les observatoires géodésiquesde l’International Laser Ranging Service (ILRS). Ce transfert de temps est effectué à l’aide deliens spatiaux optiques obtenus par l’expérience de Transfert de Temps par Lien Laser (T2L2).T2L2 a été lancée le 20 Juin 2008 à 1336 km d’altitude à bord du satellite océanographiqueJason-2. Le principe de cette expérience est basé sur la datation, au sol dans les stations laseret à bord du satellite, d’impulsions laser très courtes (30 - 100 ps) aller - retour (2 voies) venantde 25 stations laser réparties sur le Globe. La performance du lien sol-bord (dont la stabilitéatteint des valeurs inférieures à 10 ps sur 100 s), procurée par la technologie laser d’une partet par la qualité de l’instrument spatial d’autre part permet de lire précisément les variationsde l’oscillateur bord (à quartz) développé pour le système d’orbitographie et de localisationDoppler Orbitography and Radiopositionning Integrated by Satellite (DORIS) du Centre Nationald’Études Spatiales (CNES). Nous montrons qu’il est possible de construire un modèle defréquence déterministe, à court terme (10 j) et moyen terme (plusieurs mois) d’évolution de lafréquence de l’oscillateur bord DORIS, avec une précision relative de 3 - 5·10≠13. Les variationsde fréquence sont induites par un environnement spatial complexe, où les radiations, la températureet le vieillissement du résonateur dégradent l’oscillateur. L’intégration de ce modèlenous permet la réalisation d’un temps à bord pour synchroniser le réseau ILRS complet et ainsiestimer les biais en temps des stations laser par rapport à l’Universal Time Coordinate (UTC).L’effet des biais en temps, estimé à l’aide de T2L2 sur l’orbite ainsi que sur les coordonnées desstations laser de l’International Terrestrial Reference Frame (ITRF) est déterminé précisémentau niveau de quelques millimètres. Enfin T2L2 étant également capable de dater le Pulse ParSeconde (PPS) du système Global Positionning System (GPS), nous étudions l’évolution sur lelong terme (plusieurs années) des horloges utilisées dans les stations laser et nous montrons lesproblèmes insoupçonnés de l’instabilité de leur système de temps/fréquence au sol. / The purpose of my Ph.D. works is the realization of a intercontinental time transfer,with a stability better than 2 ns over 10,000 s, between the International Laser RangingService (ILRS) geodetics observatories. This time transfer is performed thanks to optical spacelinks and the Time Transfer by Laser Link (T2L2) experiment. T2L2 is a passenger on-board theoceanographic satellite Jason-2, which was launched the 20th June 2008, at 1336 km of altitude.The principle of this experiment is based on the (two-way) short laser pulses (30 - 100 ps) timetagging, in laser station on ground and on-board the satellite, which come from 25 worldwidelaser stations. The high performance of the ground-to-space link (where the stability reach valuesbetter than 10 ps over 100 s), given by the laser technology in one hand, and the quality of thespace instrument in the other hand, allows to precisely read the frequency variations of the onboardoscillators (quartz) built for the orbitography and localization Doppler Orbitography andRadiopositionning Integrated by Satellite (DORIS) French system. We demonstrate the possibilityto build a deterministic frequency model, on the short term (10 days), mid-term (severalsmonth) for the on-board DORIS oscillator frequency evolution, with a relative precision at 3- 5·10≠13. Frequency variations are caused by a complex space environment, where radiations,temperature and device aging damage the oscillator. The integration of this model allows us tobuild an "on-orbit" time realization to synchronize the whole ILRS network and thus, estimatelaser station time biases in regard to the Universal Time Coordinate (UTC). The time bias effects,estimate thanks to T2L2, on the International Terrestrial Reference Frame (ITRF) stationcoordinates, is precisely determined at the level of a few millimeters. Finally, T2L2 is able totime tagged the Global Positionning System (GPS) Pulse Per Second (PPS) signal in order tostudy the clock long term (several years) behavior in laser station and we show the unexpectedproblems due to the instability of the station time and frequency system.

Most organisms, from cyanobacteria to humans are equipped with circadian clocks. These endogenous and self-sustained pacemakers allow organisms to adapt their physiology and behavior to daily environmental variations, and to anticipate them. The circadian clock is synchronized by environmental cues (i.e. light and temperature fluctuations). The fruit fly, Drosophila melanogaster, is well established as a model for the study of circadian rhythms. Molecular mechanisms of the Drosophilacircadian clock are conserved in mammals. Using genetic screens, several essential clock proteins (PER, TIM, CLK, CYC, DBT, SGG and CK-II) were identified in flies. Homologs of most of these proteins are also involved in generating mammalian circadian rhythms. In addition, there are only six neuronal groups in the adult fly brain (comprising about 75 pairs of cells) that express high levels of clock genes. The simplicity of this system is ideal for the study of the neural circuitry underlying behavior. The first half of this dissertation focuses on a genetic screen designed to identify novel genes involved in the circadian light input pathway. The screen was based on previous observations that a mutation in the circadian photoreceptor CRYPTOCHROME (CRY) allows flies to remain rhythmic in constant light (LL), while wild type flies are usually arrhythmic under this condition. 2000 genes were overexpressed and those that showed a rhythmic behavior in LL (like crymutants) were isolated. The candidate genes isolated in the screen present a wide variety of biological functions. These include genes involved in protein degradation, signaling pathways, regulation of transcription, and even a pacemaker gene. In this dissertation, I describe work done in order to validate and characterize such candidates. The second part of this dissertation focuses on identifying the pacemaker neurons that drive circadian rhythms in constant light (LL) when the pacemaker gene period is overexpressed. We found that a subset of pacemaker neurons, the DN1s, is responsible for driving rhythms in constant light. This attractive finding reveals a novel role for the DN1s in driving behavioral rhythms under constant conditions and suggests a mechanism for seasonal adaptation in Drosophila.

Nous présentons deux contributions dans le domaine de la programmation parallèle. La première est théorique : nous introduisons l’analyse SIPS, une approche nouvelle pour dénombrer le nombre d’opérations de synchronisation durant l’exécution d’un algorithme parallèle ordonnancé par vol de travail. Basée sur le concept d’horloges logiques, elle nous permet : d’une part de donner de nouvelles majorations de coût en moyenne; d’autre part de concevoir des programmes parallèles plus efficaces par adaptation dynamique de la granularité. La seconde contribution est pragmatique : nous présentons une parallélisation générique d’algorithmes pour la génération déterministe de nombres pseudo-aléatoires, indépendamment du nombre de processus concurrents lors de l’exécution. Alternative à l’utilisation d’un générateur pseudo-aléatoire séquentiel par processus, nous introduisons une API générique, appelée Par-R qui est conçue et analysée grâce à SIPS. Sa caractéristique principale est d’exploiter un générateur séquentiel qui peut “sauter” directement d’un nombre à un autre situé à une distance arbitraire dans la séquence pseudo-aléatoire. Grâce à l’analyse SIPS, nous montrons qu’en moyenne, lors d’une exécution par vol de travail d’un programme très parallèle (dont la profondeur ou chemin critique est très petite devant le travail ou nombre d’opérations), ces opérations de saut sont rares. Par-R est comparé au générateur pseudo-aléatoire DotMix écrit pour Cilk Plus, une extension de C/C++ pour la programmation parallèle par vol de travail. Le surcout théorique de Par-R se compare favorablement au surcoput de DotMix, ce qui apparait aussi expériemntalement. De plus, étant générique, Par-R est indépendant du générateur séquentiel sous-jacent. / Nós apresentamos duas contribuições para a área de programação paralela. A primeira contribuição é teórica: nós introduzimos a análise SIPS, uma nova abordagem para a estimar o número de sincronizações realizadas durante a execução de um algoritmo paralelo. SIPS generaliza o conceito de relógios lógicos para contar o número de sincronizações realizadas por um algoritmo paralelo e é capaz de calcular limites do pior caso mesmo na presença de execuções paralelas não-determinísticas, as quais não são geralmente cobertas por análises no estado-da-arte. Nossa análise nos permite estimar novos limites de pior caso para computações escalonadas pelo popular algoritmo de roubo de tarefas e também projetar programas paralelos e adaptáveis que são mais eficientes. A segunda contribuição é pragmática: nós apresentamos uma estratégia de paralelização eficiente para a geração de números pseudoaleatórios. Como uma alternativa para implementações fixas de componentes de geração aleatória nós introduzimos uma API chamada Par-R, projetada e analisada utilizando-se SIPS. Sua principal idea é o uso da capacidade de um gerador sequencial R de realizar um “pulo” eficiente dentro do fluxo de números gerados; nós os associamos a operações realizadas pelo escalonador por roubo de tarefas, o qual nossa análise baseada em SIPS demonstra ocorrer raramente em média. Par-R é comparado com o gerador paralelo de números pseudoaleatórios DotMix, escrito para a plataforma de multithreading dinâmico Cilk Plus. A latência de Par-R tem comparação favorável à latência do DotMix, o que é confirmado experimentalmente, mas não requer o uso subjacente fixado de um dado gerador aleatório. / We present two contributions to the field of parallel programming. The first contribution is theoretical: we introduce SIPS analysis, a novel approach to estimate the number of synchronizations performed during the execution of a parallel algorithm. Based on the concept of logical clocks, it allows us: on one hand, to deliver new bounds for the number of synchronizations, in expectation; on the other hand, to design more efficient parallel programs by dynamic adaptation of the granularity. The second contribution is pragmatic: we present an efficient parallelization strategy for pseudorandom number generation, independent of the number of concurrent processes participating in a computation. As an alternative to the use of one sequential generator per process, we introduce a generic API called Par-R, which is designed and analyzed using SIPS. Its main characteristic is the use of a sequential generator that can perform a “jump-ahead” directly from one number to another on an arbitrary distance within the pseudorandom sequence. Thanks to SIPS, we show that, in expectation, within an execution scheduled by work stealing of a “very parallel” program (whose depth or critical path is subtle when compared to the work or number of operations), these operations are rare. Par-R is compared with the parallel pseudorandom number generator DotMix, written for the Cilk Plus dynamic multithreading platform. The theoretical overhead of Par-R compares favorably to DotMix’s overhead, what is confirmed experimentally, while not requiring a fixed generator underneath.

Le fait d'avoir une généalogie datée des organismes vivants est l'un des principaux objectifs de la biologie évolutive. Cette entreprise est confrontée à deux défis majeurs. Le premier est la rareté et l'incomplétude des enregistrements fossiles, pratiquement inexistants pour les microbes et essentiels pour fournir une échelle temporelle de l'histoire de la vie. Le second est la difficulté intrinsèque d'obtenir des phylogénies d'organismes dont le génome a été largement façonné par transfert latéral de gène (TLG). L'acquisition par transfert de nouveaux gènes d'origine éloignée perturbe des arbres de gènes et rend beaucoup plus complexe la reconstruction de l'histoire des espèces. Dans ce travail de thèse, je montre comment nous pouvons utiliser ces différences entre arbres de gènes et arbres d'espèces à notre avantage pour inférer les événements anciens de TLG et comment ils peuvent fournir une nouvelle échelle de temps pour l'évolution des organismes vivants. Les transferts étant particulièrement fréquents chez les espèces dont les fossiles sont rares, ils peuvent servir de nouvelle source de datation indépendante du registre géologique pour reconstruire une phylogénie datée de la vie. Dans la première partie, je réalise une analyse à l'échelle génomique pour montrer comment les méthodes de réconciliations phylogénétiques peuvent être utilisées pour détecter les lignées correspondant aux donneurs et aux receveurs des événements de TLG. En outre, ces méthodes fournissent également une vue détaillée de la façon dont les familles de gènes évoluent le long des arbres de l'espèce. En utilisant ALE, un logiciel de réconciliation probabiliste qui prend en compte l'incertitude dans les arbres de gènes, nous sommes en mesure de cartographier les événements de duplication, de perte et de transfert dans les phylogénies des cyanobactéries et des champignons. Nous montrons également comment les méthodes qui ignorent l'information contenue dans les arbres de gènes sous-estiment la fréquence réelle des TLG. Dans la deuxième partie, je présente en détail comment le TLG porte un signal temporel et comment ce signal peut être utilisé pour inférer des arbres datés. J'introduis une nouvelle méthode appelée MaxTiC qui permet de trouver un ordonnancement des noeuds dans l'arbre des espèces qui maximise la cohérence temporelle entre les transferts. Par des simulations, nous montrons la robustesse de la méthode aux erreurs présentes dans l'arbre des espèces et le nombre de familles de gènes nécessaires pour obtenir des arbres datés fiables. Enfin, pour confirmer nos résultats, je présente différentes approches permettant de comparer les temps de divergence découlant des transferts avec ceux estimés en utilisant des horloges moléculaires. Nous effectuons une analyse phylogénomique pour détecter des milliers d'événements de TLG dans quatres groupes: les cyanobactéries, les Deltaproteobactéries, les Archées et les Champignons. Nous trouvons un large accord entre les deux méthodes de datation, ce résultat étant robuste à l'utilisation de différentes prior sur les temps de divergence et différents modèles d'horloges moléculaires relâchées. Nous montrons également que certaines des dates indiquées par l'utilisation de TLG sont en désaccord avec les horloges moléculaires tout en étant soutenues par un grand nombre de TLG. Ces résultats suggèrent que l'utilisation des TLG pourrait permettre d'améliorer les méthodes de datation, notamment pour les phylogénies anciennes et ainsi conduire à d'importants changements de notre point de vue sur l'histoire de la vie / Having a dated genealogy of living organisms is one of the major goals of evolutionary biology. This enterprise faces two major challenges. The first one is the scarcity and incompleteness of the fossil record, virtually nonexistent for microbes and essential to provide a time scale of life history. The second one is the intrinsic difficulty of obtaining phylogenies in organisms whose genome has been extensively shaped by Lateral Gene Transfer (LGT). The acquisition of new genes from distant organisms creates important differences among genes trees and complicates the reconstruction of the species history. In this thesis work I show how we can use those differences to our advantage to infer ancient events of LGT and how they provide a temporal scale of evolution. Transfers can supply an important amount of information on divergence times in organisms whose fossils are very scarce, acting as a new dating source independent of the geological record and taking us a step closer to building a whole dated phylogeny of Life. In the first part, I perform genomic-scale analyses to show how phylogenetic reconciliations can be used to detect donor and recipient lineages of LGT events. Moreover, they also provide a detailed view of how gene families evolve along species trees. Using ALE, a probabilistic reconciliation software that accounts for the uncertainty in gene trees, we are able to map events of duplication, loss and transfer in phylogenies of cyanobacteria and fungi. We also show how methods that ignore the information contained in gene trees underestimate the real frequency of LGT. In the second part, I present in detail how LGT carries a temporal signal and how this signal can be used to infer dated trees. I explain a new method called MaxTiC, that finds the best dated tree by maximizing the number of transfers that are time-compatible with a phylogeny. By simulations we show how robust the method is to errors in the species tree and how many gene families are required to obtain reliable dated trees. Finally, to confirm our results I present different metrics to compare the divergence times inferred by transfers with those inferred by molecular clocks. We perform a phylogenomic analysis to detect thousands of LGT events in cyanobacteria, Deltaproteobacteria, Archaea and fungi and obtain their dated phylogenies. We find a broad agreement between both dating methods, a result robust to the use of different priors on divergence times and different models of relaxed molecular clock. We also show that some of the dates inferred by using LGT are not recovered by molecular clocks. These results altogether suggest that the use of LGT in future dating studies may have a big impact on the inferred dates of major evolutionary events and can lead to an important change of our view of the History of Life