This dissertation examines three important issues in energy markets: price dynamics, information flow, and structural change. We discuss each issue in detail, building empirical time series models, analyzing the results, and interpreting the findings. First, we examine the contemporaneous interdependencies and information flows among crude oil, natural gas, and electricity prices in the United States (US) through the multivariate generalized autoregressive conditional heteroscedasticity (MGARCH) model, Directed Acyclic Graph (DAG) for contemporaneous causal structures and Bernanke factorization for price dynamic processes. Test results show that the DAG from residuals of out-of-sample-forecast is consistent with the DAG from residuals of within-sample-fit. The result supports innovation accounting analysis based on DAGs using residuals of out-of-sample-forecast. Second, we look at the effects of the federal fund rate and/or WTI crude oil price shock on US macroeconomic and financial indicators by using a Factor Augmented Vector Autoregression (FAVAR) model and a graphical model without any deductive assumption. The results show that, in contemporaneous time, the federal fund rate shock is exogenous as the identifying assumption in the Vector Autoregression (VAR) framework of the monetary shock transmission mechanism, whereas the WTI crude oil price return is not exogenous. Third, we examine price dynamics and contemporaneous causality among the price returns of WTI crude oil, gasoline, corn, and the S&P 500. We look for structural break points and then build an econometric model to find the consistent sub-periods having stable parameters in a given VAR framework and to explain recent movements and interdependency among returns. We found strong evidence of two structural breaks and contemporaneous causal relationships among the residuals, but also significant differences between contemporaneous causal structures for each sub-period.

Many researchers would be interested in one question: If a change of X is made, will Y be influenced in response? However, while a lot of statistical methods are developed to analyze association between variables, how to find a causal relationship among variables is relatively neglected. The PC algorithm, developed on the basis of Pearl, Sprites, Glymour, and Scheines‟s studies, is used to find the causal pattern of the real-world observed data. However, PC in Tetrad produces a class of directed acyclic graphs (DAGs) that are statistically equivalent under a normal distribution, and therefore such a distributional assumption causes a series of unidentifiable DAGs because of the same joint probability. In 2006 Shimizu, Hoyer, Hyvärinen, and Kerminen developed the Linear Independent Non-Gaussian Model (LiNGAM) to do a causal search based on the independently non-Gaussian distributed disturbances by applying higher-order moment structures. The research objective of this dissertation is to examine whether the LiNGAM is helpful relative to the PC algorithm, to detect the causal relation of non-normal data. The LiNGAM algorithm is implemented by first doing independent component analysis (ICA) estimation and then discovering the correct ordering of variables. Thus, the procedures of ICA estimation and the process of finding the correct causal orderings in LiNGAM are illustrated. Next, we do a causal search on the retail-level scanner data to investigate the pricing interaction between the manufacturer and the retailer by applying these two algorithms. While PC generates the set of indistinguishable DAGs, LiNGAM gives more exact causal patterns. This work demonstrates the algorithm based on the non-normal distribution assumption makes causal associations clearer. In Chapter IV, we apply a classical structural demand model to investigate the consumer purchase behavior in the carbonated soft drink market. Unfortunately, when further restrictions are imposed, we cannot get reasonable results as most researchers require. LiNGAM is applied to prove the existence of endogeneity for the brand‟s retail price and verify that the brand‟s wholesale price is not a proper instrument for its retail price. Therefore, consistent estimates cannot be derived as the theories suggest. These results imply that economic theory is not always found in restriction applied to observational data.

Many parallel programming languages allow programmers to describe parallelism by using constructs such as fork/join. When executed, such programs can be modeled as directed graphs, with nodes representing a computation and edges representing the sequence and dependency. However, because it does not coerce regularity in the computation, the general model is not amenable to efficient execution of the resulting program. Therefore, a more restrictive model called Series-Parallel DAG (Directed Acyclic Graph) has been proposed and adopted by several major parallel languages. As reported by the Cilk developers, many parallel computations can be easily expressed in the series-parallel model, and there are provably efficient scheduling algorithms for the SP DAGs. Nevertheless, it remains open how much inherent parallelism will be lost when conforming to the model, because expressing a computation in the series-parallel model may also induce performance losses. We will show that any general DAG can be converted into an SP DAG without violating the original precedence relations; moreover, the conversion can be carried out in essentially linear time and space, and the resulting DAG exhibits little loss in the parallelism. Since the resulting SP DAG can then be executed with high efficiency, it implies that the languages based on SP DAGs are not as restrictive as they were thought to be. / Singapore-MIT Alliance (SMA)

We present a methodology for exploiting shared-memory parallelism within matrix computations by expressing linear algebra algorithms as directed acyclic graphs. Our solution involves a separation of concerns that completely hides the exploitation of parallelism from the code that implements the linear algebra algorithms. This approach to the problem is fundamentally different since we also address the issue of programmability instead of strictly focusing on parallelization. Using the separation of concerns, we present a framework for analyzing and developing scheduling algorithms and heuristics for this problem domain. As such, we develop a theory and practice of scheduling concepts for matrix computations in this dissertation. / text

Continuous advances in VLSI technology have led to more complex digital designs and shrinking transistor sizes. Due to these developments, design verification and manufacturing test have gained more importance and 70 % of the design expenditure in on validation processes. Electronic Design Automation (EDA) tools play a huge role in the validation process with various verification and test tools. Their efficiency have a high impact in saving time and money in this competitive market. Direct Acyclic Graphs (DAGs) are the backbone for most of the EDA tools. DAG is the most efficient data structure to store circuit information and also have efficient backt traversing structure which help in developing reasoning/ debugging tools. In this thesis, we focus on two such EDA tools using graphs as their underlying structure for circuit information storage • Scan pattern Debugger for Partial Scan Designs • Circuit SAT Bounded Model Checkers We developed a complete Interactive Scan Pattern Debugger Suite currently being used in the industry for next generation microprocessor design. The back end is an implication graph based sequential logic simulator which creates a Debug Implication Graph during the logic simulation of the failing patterns. An efficient node traversal mechanism across time frames, in the DIG, is used to perform the root-cause analysis for the failing scan-cells. In addition, the debugger provides visibility into the circuit internals to understand and fix the root-cause. We integrated the proposed technique into the scan ATPG flow for industrial microprocessor designs. We were able to resolve the First Silicon logical pattern failures within hours, which would have otherwise taken a few days of manual effort for root-causing the failure, understanding the root-cause and fixing it. For our circuit SAT implementation, we replace the internal implication graph used by the SAT solver with our debug implication graph (DIG). There is a high amount of circuit unrolling in circuit SAT/ BMC (Bounded Model Checking) problems which creates copies of the same combinational blocks in multiple time frames. This allows us to use the repetitive circuit structure and club it with the CNF database in the SAT solver. We propose a new data structure to store data in a circuit SAT solver which results up to 90% reduction in number of nodes. / Master of Science

This work focuses on the use of a genetic algorithm for optimization in a search-based problem. The Genetic Algorithm (GA) is a subset of evolutionary algorithms that models biological processes to optimize highly complex functions. A GA allows a population composed of many individuals to evolve under specified selection rules to a state that maximizes the “fitness” (i.e. minimize the objective function). A major advantage of using GA over most stochastic techniques is its parallelism, which speeds up the simulation results leading to faster convergence. With mutation, the GA is also less likely to get stuck in local minima compared to other stochastic techniques. However, some notable drawbacks of the Standard GA (SGA) include slow convergence and a possibility of being stuck in local optimum solution. The SGA uses a random process to generate parameter values for the initial population generation, crossover and mutation processes. Random number generators are designed to result in either uniform distributions or Gaussian distributions. We conjecture that the evolutionary processes in genetics are driven by a random non-linear deterministic dynamic process rather than a random non-deterministic process. Therefore, in the GA evolutionary process, a chaotic map is incorporated into the initial population generation, the crossover and mutation processes of the SGA; this is termed the Chaotic GA (CGA). The properties of a chaotic system that provides additional benefits over randomly generated solutions are sensitivity to initial conditions, topological density and topological transitivity (robust diversity). These properties ensure that the CGA is able to explore the entire solution space. Introducing chaos into the whole process of a standard genetic algorithm may help improve convergence time and accuracy. Simulation was done using Matlab and Java.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / Apesar do crescente reconhecimento do potencial dos diagramas causais por epidemiologistas, essa técnica ainda é pouco utilizada na investigação epidemiológica. Uma das possíveis razões é que muitos temas de investigação exigem modelos causais complexos. Neste trabalho, a relação entre estresse ocupacional e obesidade é utilizada como um exemplo de aplicação de diagramas causais em questões relacionadas a confundimento. São apresentadas etapas da utilização dos diagramas causais, incluindo a construção do gráfico acíclico direcionado, seleção de variáveis para ajuste estatístico e a derivação das implicações estatísticas de um diagrama causal. A principal vantagem dos diagramas causais é tornar explícitas as hipóteses adjacentes ao modelo considerado, permitindo que suas implicações possam ser analisadas criticamente, facilitando, desta forma, a identificação de possíveis fontes de viés e incerteza nos resultados de um estudo epidemiológico. / Despite the increasing recognition of the potential of causal diagrams by epidemiologists, this technique has not been widely used in epidemiological research. One possible reason is that many research topics require complex causal models. In this article, the relationship between occupational stress and obesity is used as an example of application of causal diagrams on confounding. Some steps are presented, including the construction of the directed acyclic graph, the selection of variables for statistical control and the derivation of the statistical implications of a causal diagram. The main advantage of causal diagrams is to make the assumptions explicit, thus facilitating critical evaluations and the identification of possible sources of bias and uncertainty in the results of an epidemiological study.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / Apesar do crescente reconhecimento do potencial dos diagramas causais por epidemiologistas, essa técnica ainda é pouco utilizada na investigação epidemiológica. Uma das possíveis razões é que muitos temas de investigação exigem modelos causais complexos. Neste trabalho, a relação entre estresse ocupacional e obesidade é utilizada como um exemplo de aplicação de diagramas causais em questões relacionadas a confundimento. São apresentadas etapas da utilização dos diagramas causais, incluindo a construção do gráfico acíclico direcionado, seleção de variáveis para ajuste estatístico e a derivação das implicações estatísticas de um diagrama causal. A principal vantagem dos diagramas causais é tornar explícitas as hipóteses adjacentes ao modelo considerado, permitindo que suas implicações possam ser analisadas criticamente, facilitando, desta forma, a identificação de possíveis fontes de viés e incerteza nos resultados de um estudo epidemiológico. / Despite the increasing recognition of the potential of causal diagrams by epidemiologists, this technique has not been widely used in epidemiological research. One possible reason is that many research topics require complex causal models. In this article, the relationship between occupational stress and obesity is used as an example of application of causal diagrams on confounding. Some steps are presented, including the construction of the directed acyclic graph, the selection of variables for statistical control and the derivation of the statistical implications of a causal diagram. The main advantage of causal diagrams is to make the assumptions explicit, thus facilitating critical evaluations and the identification of possible sources of bias and uncertainty in the results of an epidemiological study.

In telecommunications, there is currently a lot of work being done to migrate to the cloud, and a lot of specialized hardware is being exchanged for virtualized solutions. One important part of telecommunication networks that is yet to be moved to the cloud is known as the base-band unit, which sits between the antennas and the core network. The base-band unit has very strict latency requirements, making it unsuitable for out-of-the-box cloud solutions. Ericsson is therefore investigating if cloud solutions can be customized in such a way that base-band unit functionality can be virtualized as well. One such customization is to describe the functionality of a base-band unit using a directed acyclic graph (DAG), and deploy it to a cloud environment using Kubernetes. This thesis sets out to take applications represented using a DAG and deploy it using Kubernetes in such a way that the network latency is reduced when compared to the deployment generated by the default Kubernetes scheduler. The problem of placing the applications onto the available hardware resources was formulated as an integer linear programming problem. The problem was then implemented using Pyomo and solved with the open-source solver GLPK to obtain an optimized placement. This placement was then used to generate a configuration file that could be used to deploy the applications using Kubernetes. A mock application was developed in order to evaluate the optimized placement. The evaluation carried out in this thesis shows that the optimized placement obtained from the solution could improve the average round-trip latency of applications represented using a DAG by up to 30% when compared to the default Kubernetes scheduler.

Advanced architecture processors provide features such as caches and branch prediction that result in improved, but variable, execution time of software. Hard real-time systems require tasks to complete within timing constraints. Consequently, hard real-time systems are typically designed conservatively through the use of tasks? worst-case execution times (WCET) in order to compute deterministic schedules that guarantee task?s execution within giving time constraints. This use of pessimistic execution time assumptions provides real-time guarantees at the cost of decreased performance and resource utilization. In soft real-time systems, however, meeting deadlines is not an absolute requirement (i.e., missing a few deadlines does not severely degrade system performance or cause catastrophic failure). In such systems, a guaranteed minimum probability of completing by the deadline is sufficient. Therefore, there is considerable latitude in such systems for improving resource utilization and performance as compared with hard real-time systems, through the use of more realistic execution time assumptions. Given probability distribution functions (PDFs) representing tasks? execution time requirements, and tasks? communication and precedence requirements, represented as a directed acyclic graph (DAG), this dissertation proposes and investigates algorithms for constructing non-preemptive stochastic schedules. New PDF manipulation operators developed in this dissertation are used to compute tasks? start and completion time PDFs during schedule construction. PDFs of the schedules? completion times are also computed and used to systematically trade the probability of meeting end-to-end deadlines for schedule length and jitter in task completion times. Because of the NP-hard nature of the non-preemptive DAG scheduling problem, the new stochastic scheduling algorithms extend traditional heuristic list scheduling and genetic list scheduling algorithms for DAGs by using PDFs instead of fixed time values for task execution requirements. The stochastic scheduling algorithms also account for delays caused by communication contention, typically ignored in prior DAG scheduling research. Extensive experimental results are used to demonstrate the efficacy of the new algorithms in constructing stochastic schedules. Results also show that through the use of the techniques developed in this dissertation, the probability of meeting deadlines can be usefully traded for performance and jitter in soft real-time systems.