This thesis studies the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. Although the number of constraints is reduced, the problem becomes more difficult to solve due to the enlarged solution space. Perhaps, the only previous study used a very primitive delay model which could not handle difficult instances when sink groups are intermingled. We reuse existing techniques to solve this problem including difficult instances based on an improved delay model. Experimental results show that our algorithm can reduce the total clock routing wirelength by 9%–15% compared to greedy-DME, which is one of the best zero skew routing algorithms.

Clock synchronization is one of fundamental requirements in distributed networks. However, the imperfection of crystal oscillators is a potential hurdle for network-wide collaboration and degrades the performance of cooperative applications. Since clock discrepancy among nodes is inevitable, many software and hardware attempts have been introduced to meet synchronization requirements. Most of the attempts are built on communication protocols that demand timestamp exchanges to improve synchronization accuracy or resource efficiency. However, link delay and environmental changes sometimes impede these synchronization efforts that achieve in desired accuracy. First, the clock synchronization problem was examined in networks where nodes lack the high accuracy oscillators or programmable network interfaces some previous protocols depend on. Next, a stochastic and practical clock model was developed by using information criteria which followed the principle of Occam's razor. The model was optimized in terms of the number of parameters. Simulation by using real measurements on low-powered micro-controllers validated the derived clock model. Last, based on the model, a clock tracking algorithm was proposed to achieve high synchronization accuracy between unstable clocks. This algorithm employed the Kalman filter to track clock offset and skew. Extensive simulations demonstrated that the proposed synchronization algorithm not only could follow the clock uncertainties shown in real measurements but also was tolerant to corrupted timestamp deliveries. Clock oscillators are vulnerable to noises and environmental changes. As a second approach, clock estimation technique that took circumstances into consideration was proposed. Through experiments on mobile devices, the obstacles were clarified in synchronization over wireless networks. While the causes of clock inaccuracy were focused on, the effect of environmental changes on clock drifting was investigated. The analysis of the observations inspired an M-estimator of clock error that was accurate but under dominant disturbances such as oscillator instability and random network delay. A Kalman filter was designed to compensate with temperature changes and estimate clock offset and skew. The proposed temperature-compensated Kalman filter achieved the better estimates of clock offset and skew by adjusting frequency shifts caused by temperature changes. The proposed Kalman filter-based clock synchronization was implemented in C. A real-time operation was proved by clock tracking between two mobile platforms that the synchronization technique was implemented on. Moreover, the technique was converted to fixed-point algorithm, which might degrade performance, to evaluate the synchronizing operation on fixed-point processors. The fixed-point simulation reported performance degradation caused by limited hardware resources; however, it also corroborated the applicability of the synchronization technique.

京都大学 / 0048 / 新制・課程博士 / 博士(薬科学) / 甲第18923号 / 薬科博第37号 / 新制||薬||5(附属図書館) / 31874 / 京都大学大学院薬学研究科医薬創成情報科学専攻 / (主査)教授 岡村 均, 教授 中山 和久, 教授 竹島 浩 / 学位規則第4条第1項該当 / Doctor of Pharmaceutical Sciences / Kyoto University / DFAM

No description available.

No description available.

No description available.

No description available.

Molecular and paleontological approaches have produced extremely different estimates for divergence times among orders of placental mammals and within rodents with molecular studies suggesting a much older date than fossils. We evaluated the conflict between the fossil record and molecular data and find a significant correlation between dates estimated by fossils and relative branch lengths, suggesting that molecular data agree with the fossil record regarding divergence times in rodents. Our approach includes a correction for tree hierarchy involving simulating the random appearance of fossils. We also present a ghost lineage approach that attempts to incorporate the potential for the discovery of older fossils into a Bayesian analysis of divergence dates. Applying this approach to a set of Eocene rodent fossils, we estimated the earliest divergence in rodents appears to have occurred at approximately the K/T boundary, but interordinal splits were estimated to have taken place late in the Cretaceous. We propose that some molecular clock studies may overestimate divergence times due to periods of accelerated molecular evolution across multiple lineages or due to saturation of data that is not adequately corrected by the evolutionary model. We have sequenced the complete mitochondrial genomes of three rodent species, Anomalurus beecrofti, Castor canadensis, and Dipodomys ordii, and attempt to resolve phylogenetic relationships within rodents using the mitochondrial genome, a nuclear dataset of comparable size, and a combined analysis containing 26 kbp of sequence data. The combined analysis recovered a Sciuromorpha – Hystricomorpha clade with strong support. Our data suggest that increased character sampling improves resolution at these early nodes while better taxon sampling of mitochondrial genomes has led to better supported clades that converge on conclusions obtained from nuclear datasets. Several molecular studies have concluded that the zokors, genus Myospalax, evolved from within the rodent subfamily Cricetinae. We tested this conclusion using mitochondrial data and determined that Myospalax is sister to a clade containing the subfamilies Spalacinae and Rhizomyinae, and all three of these lineages appear to be basal to the superfamily Muroidea. Based on the position of these three lineages, we suggested that they be placed in a distinct family, the Spalacidae. The murine genera Mus and Rattus are thought to have diverged about 12 million years ago (Ma) based on a series of fossils from the Siwaliks of Pakistan, but assumptions of murid relationships that led to this conclusion have been shown to be false by molecular data. Equally parsimonious hypotheses can be proposed which place the 12 million year old Progonomys fossil at the base of the family Muridae, basal to the subfamily Murinae, or at the Mus - Rattus divergence. We here test the dates of evolutionary divergences in murids. Our results indicate that the family Muridae probably diverged earlier than the Siwalik fossils, but Mus and Rattus diverged at the same time or prior to the 12 Ma fossil date. We also cannot reject the hypothesis that the 12 Ma date represents the oldest split in the Murinae instead of the more derived Mus – Rattus date. We also recovered phylogenetic results suggesting that Taterillus is related to the tribe Gerbillini and not to other genera that are treated as Taterillini and that Gerbillurus evolved from within Gerbilliscus.

The circadian oscillator of the cyanobacterium Synechococcus elongatus is composed of only three proteins, KaiA, KaiB, and KaiC, which together with ATP can generate a self-sustained ~24 hour oscillation of KaiC phosphorylation for several days. KaiA induces KaiC to autophosphorylate whereas KaiB blocks the stimulation of KaiC by KaiA, which allows KaiC to autodephosphorylate. We propose and support a model in which the C-terminal loops of KaiC, the “A-loops”, are the master switch that determines overall KaiC activity. When the A-loops are in their buried state, KaiC is an autophosphatase. When the A-loops are exposed, however, KaiC is an autokinase. The data suggest that KaiA stabilizes the exposed state of the A-loops through direct binding. We also show evidence that if KaiA cannot stabilize the exposed state KaiC remains hypophosphorylated. We propose that KaiB inactivates KaiA by preventing it from stabilizing the exposed state of the A-loops. Thus, KaiA and KaiB likely act by shifting the dynamic equilibrium of the A-loops between exposed and buried states, which shifts the balance of autokinase and autophosphatase activities of KaiC. A-loop exposure likely moves the ATP closer to the sites of phosphorylation and we show evidence in support of how this movement may be accomplished. Density functional theory calculations of isolated Watson–Crick A:U and A:T base pairs predict that adenine 13C2 trans-hydrogen bond deuterium isotope shifts due to isotopic substitution at the pyrimidine H3, 2hΔ13C2, are sensitive to the hydrogen-bond distance between the N1 of adenine and the N3 of uracil or thymine, which supports the notion that 2hΔ13C2 is sensitive to hydrogen-bond strength. Calculated 2hΔ13C2 values at a given N1–N3 distance are the same for isolated A:U and A:T base pairs. Replacing uridine residues in RNA with 5-methyl uridine and substituting deoxythymidines in DNA with deoxyuridines do not statistically shift empirical 2hΔ13C2 values. Thus, we show experimentally and computationally that the C7 methyl group of thymine has no measurable affect on 2hΔ13C2 values. Furthermore, 2hΔ13C2 values of modified and unmodified RNA are more negative than those of modified and unmodified DNA, which supports our hypothesis that RNA hydrogen bonds are stronger than those of DNA. It is also shown here that 2hΔ13C2 is context dependent and that this dependence is similar for RNA and DNA.

Clock Distribution Network (CDN) is an important component of any synchronous logic circuit. The function of CDN is to deliver the clock signal to the clock sinks. Clock skew is defined as the difference in the arrival time of the clock signal at the clock sinks. Higher uncertainty in skew (due to PVT variations) degrades circuit performance by decreasing the maximum possible delay between any two sequential elements. Aggressive frequency scaling has also led to high power consumption especially in CDN. This dissertation addresses variation and power issues in the design of current and potential future CDN. The research detailed in this work presents algorithmic techniques for the following problems: (1) Variation tolerance in useful skew design, (2) Link insertion for buffered clock nets, (3) Methodology and algorithms for rotary clocking and (4) Clock mesh optimization for skew-power trade off. For clock trees this dissertation presents techniques to integrate the different aspects of clock tree synthesis (skew scheduling, abstract topology and layout embedding) into one framework- tolerance to variations. This research addresses the issues involved in inserting cross-links in a buffered clock tree and proposes design criteria to avoid the risk of short-circuit current. Rotary clocking is a promising new clocking scheme that consists of unterminated rings formed by differential transmission lines. Rotary clocking achieves reduction in power dissipation clock skew. This dissertation addresses the issues in adopting current CAD methodology to rotary clocks. Alternative methodology and corresponding algorithmic techniques are detailed. Clock mesh is a popular form of CDN used in high performance systems. The problem of simultaneous sizing and placement of mesh buffers in a clock mesh is addressed. The algorithms presented remove the edges from the clock mesh to trade off skew tolerance for low power. For clock trees as well as link insertion, our experiments indicate significant reduction in clock skew due to variations. For clock mesh, experimental results indicate 18.5% reduction in power with 1.3% delay penalty on a average. In summary, this dissertation details methodologies/algorithms that address two critical issues- variation and power dissipation in current and potential future CDN.