Objectives. The goal in radiotherapy is to deliver adequate radiation to the tumor volume while limiting damage to the surrounding healthy tissue. However, this goal is challenged by respiratory-induced motion. The objective of this work was to identify whether motion in electronic portal images can be tracked with an optical flow algorithm and whether a neural network can predict tumor motion. Methods. A multi-resolution optical flow algorithm that incorporates weighting based on the differences between image frames was used to automatically sample the vectors corresponding to the motion. The global motion was obtained by computing the average weighted mean from the set of vectors. The algorithm was evaluated using tumor trajectories taken from seven lung cancer patients, a 3D printed patient tumor and a virtual dynamic multi-leaf collimator (DMLC) system. The feasibility of detecting and tracking motion at the field edge was examined with a proof-of-concept implementation that included (1) an algorithm that detected local motion, and (2) a control algorithm that adapted the virtual MLC. To compensate for system latency, a generalized neural network, using both offline (treatment planning data) and online (during treatment delivery) learning, was implemented for tumor motion prediction. Results and Conclusions. The algorithm tracked the global motion of the target with an accuracy of around 0.5 mm. While the accuracy is similar to other methods, this approach does not require manual delineation of the target and can, therefore, provide real-time autonomous motion estimation during treatment. Motion at the treatment field edge was tracked with an accuracy of -0.4 ± 0.3 mm. This proof-of-concept simulation demonstrated that it is possible to adapt MLC leaves based on the motion detected at the field edges. Unplanned intrusions of external organs-at-risk could be shielded. A generalized network with a prediction error of 0.59 mm, and a shorter initial learning period (compared to previous studies) was achieved. This network may be used as a plug-and-play predictor in which tumor position could be predicted at the start of treatment and the need for pretreatment data and optimization for individual patients may be avoided. / February 2017

Worst-case analysis is often meaningless in practice. Some problems never reach the anticipated worst-case complexity. Other solutions get bogged down with impractical constants during implementation, despite having favorable asymptotic running times. In this thesis, we investigate these contrasts in the context of finding maximum flows in planar digraphs. We suggest analytic techniques that adapt to the problem instance, and present a structural property that concludes equivalence between shortest paths and maximum st-flow in planar graphs. The best known algorithm for maximum st-flow in directed planar graphs is an augmenting- paths algorithm with O(n) iterations. Using dynamic trees, each iteration can be implemented in O(log n) time. Long before, Itai and Shiloach showed that when s and t are on the boundary of a common face, the O(n)-iteration augmenting-paths algorithm is equivalent to Dijkstra's algorithm in the graph���s dual: the max st-planar st-flow problem can be solved with one single-source shortest-path computation. In this thesis we show that (a) when s and t are separated by p faces, the max st-flow can be found with at most 2p single-source shortest-path computations, which, using the linear-time shortest-paths algorithm for planar graphs, results in an O(np)-time algorithm, and (b) that the equivalence between augmenting-paths and Dijkstra's extends to the most general non-st-planar digraphs, using their half-infinite universal cover graph. / Graduation date: 2013

abstract: Power flow calculation plays a significant role in power system studies and operation. To ensure the reliable prediction of system states during planning studies and in the operating environment, a reliable power flow algorithm is desired. However, the traditional power flow methods (such as the Gauss Seidel method and the Newton-Raphson method) are not guaranteed to obtain a converged solution when the system is heavily loaded. This thesis describes a novel non-iterative holomorphic embedding (HE) method to solve the power flow problem that eliminates the convergence issues and the uncertainty of the existence of the solution. It is guaranteed to find a converged solution if the solution exists, and will signal by an oscillation of the result if there is no solution exists. Furthermore, it does not require a guess of the initial voltage solution. By embedding the complex-valued parameter α into the voltage function, the power balance equations become holomorphic functions. Then the embedded voltage functions are expanded as a Maclaurin power series, V(α). The diagonal Padé approximant calculated from V(α) gives the maximal analytic continuation of V(α), and produces a reliable solution of voltages. The connection between mathematical theory and its application to power flow calculation is described in detail. With the existing bus-type-switching routine, the models of phase shifters and three-winding transformers are proposed to enable the HE algorithm to solve practical large-scale systems. Additionally, sparsity techniques are used to store the sparse bus admittance matrix. The modified HE algorithm is programmed in MATLAB. A study parameter β is introduced in the embedding formula βα + (1- β)α^2. By varying the value of β, numerical tests of different embedding formulae are conducted on the three-bus, IEEE 14-bus, 118-bus, 300-bus, and the ERCOT systems, and the numerical performance as a function of β is analyzed to determine the “best” embedding formula. The obtained power-flow solutions are validated using MATPOWER. / Dissertation/Thesis / Flow chart of the HE algorithm / Presentation for mater's thesis defense / Masters Thesis Electrical Engineering 2015

No description available.

Storage systems used for supercomputers and high performance computing (HPC) centers exhibit load imbalance and resource contention. This is mainly due to two factors: the bursty nature of the I/O of scientific applications; and the complex and distributed I/O path without centralized arbitration and control. For example, the extant Lustre parallel storage system, which forms the backend storage for many HPC centers, comprises numerous components, all connected in custom network topologies, and serve varying demands of large number of users and applications. Consequently, some storage servers can be more loaded than others, creating bottlenecks, and reducing overall application I/O performance. Existing solutions focus on per application load balancing, and thus are not effective due to the lack of a global view of the system. In this thesis, we adopt a data-driven quantitative approach to load balance the I/O servers at extreme scale. To this end, we design a global mapper on Lustre Metadata Server (MDS), which gathers runtime statistics collected from key storage components on the I/O path, and applies Markov chain modeling and a dynamic maximum flow algorithm to decide where data should be placed in a load-balanced fashion. Evaluation using a realistic system simulator shows that our approach yields better load balancing, which in turn can help yield higher end-to-end performance. / Master of Science / Critical jobs such as meteorological prediction are run at exa-scale supercomputing facilities like Oak Ridge Leadership Computing Facility (OLCF). It is necessary for these centers to provide an optimally running infrastructure to support these critical workloads. The amount of data that is being produced and processed is increasing rapidly necessitating the need for these High Performance Computing (HPC) centers to design systems to support the increasing volume of data. Lustre is a parallel filesystem that is deployed in HPC centers. Lustre being a hierarchical filesystem comprises of a distributed layer of Object Storage Servers (OSSs) that are responsible for I/O on the Object Storage Targets (OSTs). Lustre employs a traditional capacity-based Round-Robin approach for file placement on the OSTs. This results in the usage of only a small fraction of OSTs. Traditional Round-Robin approach also increases the load on the same set of OSSs which results in a decreased performance. Thus, it is imperative to have a better load balanced file placement algorithm that can evenly distribute the load across all OSSs and the OSTs in order to meet the future demands of data storage and processing. We approach the problem of load imbalance by splicing the whole system into two views: filesystem and applications. We first collect the current usage statistics of the filesystem by means of a distributed monitoring tool. We then predict the applications’ I/O request pattern by employing a Markov Chain Model. Finally, we make use of both these components to design a load balancing algorithm that eventually evens out the load on both the OSSs and OSTs. We evaluate our algorithm on a custom-built simulator that simulates the behavior of the actual filesystem.

Current approaches integrating large scale data and information from a variety of sources to reveal molecular basis of cellular events do not adequately benefit from pathway information. Here, we portray a network structure based pathway enrichment system that fuses and exploits model and data: signalling pathways are taken as the biological models while microarray and ChIP-seq data are the sample input data sources among many other alternatives. Our model- and data-driven hybrid system allows to quantitatively assessing the biological activity of a cyclic pathway and simultaneous enrichment of the significant paths leading to the ultimate cellular response. Signal Transduction Score Flow (SiTSFlow) algorithm is the fundamental constituent of proposed network structure based pathway enrichment system. SiTSFlow algorithm converts each pathway into a cascaded graph and then gene scores are mapped onto the protein nodes. Gene scores are transferred to en route of the pathway to form a final activity score describing behaviour of a specific process in the pathway while enriching of the gene node scores. Because of cyclic pathways, the algorithm runs in an iterative manner and it terminates when the node scores converge. The converged final activity score provides a quantitative measure to assess the biological significance of a process under the given experimental conditions. The conversion of cyclic pathways into cascaded graphs is performed by using a linear time multiple source Breadth First Search Algorithm. Furthermore, proposed network structure based pathway enrichment system works in linear time in terms of nodes and edges of given pathways. In order to explore various biological responses of several processes in a global signalling network, the selected small pathways have been unified based on their common gene and process nodes. The merge algorithm for pathways also runs in linear time in terms of nodes and edges of given pathways. In the experiments, SiTSFlow algorithm proved the convergence behaviour of activity scores for several cyclic pathways and for a global signalling network. The biological results obtained by assessing of experimental data by described network structure based pathway enrichment system were in correlation with the expected cellular behaviour under the given experimental conditions.

No description available.

Network on Chips[1][2][3][4] are critical elements of modern System on Chip(SoC) as well as Chip Multiprocessor(CMP)designs. Network on Chips (NoCs) help manage high complexity of designing large chips by decoupling computation from communication. SoCs and CMPs have a multiplicity of communicating entities like programmable processing elements, hardware acceleration engines, memory blocks as well as off-chip interfaces. With power having become a serious design constraint[5], there is a great need for designing NoC which meets the target communication requirements, while minimizing power using all the tricks available at the architecture, microarchitecture and circuit levels of the de-sign. This thesis presents a holistic, QoS based, power optimal design solution of a NoC inside a CMP taking into account link microarchitecture and processor tile configurations. Guaranteeing QoS by NoCs involves guaranteeing bandwidth and throughput for connections and deterministic latencies in communication paths. Label Switching based Network-on-Chip(LS-NoC) uses a centralized LS-NoC Management framework that engineers traffic into QoS guaranteed routes. LS-NoC uses label switching, enables band-width reservation, allows physical link sharing and leverages advantages of both packet and circuit switching techniques. A flow identification algorithm takes into account band-width available in individual links to establish QoS guaranteed routes. LS-NoC caters to the requirements of streaming applications where communication channels are fixed over the lifetime of the application. The proposed NoC framework inherently supports heterogeneous and ad-hoc SoC designs. A multicast, broadcast capable label switched router for the LS-NoC has been de-signed, verified, synthesized, placed and routed and timing analyzed. A 5 port, 256 bit data bus, 4 bit label router occupies 0.431 mm2 in 130nm and delivers peak band-width of80Gbits/s per link at312.5MHz. LS Router is estimated to consume 43.08 mW. Bandwidth and latency guarantees of LS-NoC have been demonstrated on streaming applications like Hiper LAN/2 and Object Recognition Processor, Constant Bit Rate traffic patterns and video decoder traffic representing Variable Bit Rate traffic. LS-NoC was found to have a competitive figure of merit with state-of-the-art NoCs providing QoS. We envision the use of LS-NoC in general purpose CMPs where applications demand deterministic latencies and hard bandwidth requirements. Design variables for interconnect exploration include wire width, wire spacing, repeater size and spacing, degree of pipelining, supply, threshold voltage, activity and coupling factors. An optimal link configuration in terms of number of pipeline stages for a given length of link and desired operating frequency is arrived at. Optimal configurations of all links in the NoC are identified and a power-performance optimal NoC is presented. We presents a latency, power and performance trade-off study of NoCs using link microarchitecture exploration. The design and implementation of a framework for such a design space exploration study is also presented. We present the trade-off study on NoCs by varying microarchitectural(e.g. pipelining) and circuit level(e.g. frequency and voltage) parameters. A System-C based NoC exploration framework is used to explore impacts of various architectural and microarchitectural level parameters of NoC elements on power and performance of the NoC. The framework enables the designer to choose from a variety of architectural options like topology, routing policy, etc., as well as allows experimentation with various microarchitectural options for the individual links like length, wire width, pitch, pipelining, supply voltage and frequency. The framework also supports a flexible traffic generation and communication model. Latency, power and throughput results using this framework to study a 4x4 CMP are presented. The framework is used to study NoC designs of a CMP using different classes of parallel computing benchmarks[6]. One of the key findings is that the average latency of a link can be reduced by increasing pipeline depth to a certain extent, as it enables link operation at higher link frequencies. Abstract There exists an optimum degree of pipelining which minimizes the energy-delay product of the link. In a 2D Torus when the longest link is pipelined by 4 stages at which point least latency(1.56 times minimum) is achieved and power(40% of max) and throughput (64%of max) are nominal. Using frequency scaling experiments, power variations of up to40%,26.6% and24% can be seen in 2D Torus, Reduced 2D Torus and Tree based NoC between various pipeline configurations to achieve same frequency at constant voltages. Also in some cases, we find that switching to a higher pipelining configuration can actually help reduce power as the links can be designed with smaller repeaters. We also find that the overall performance of the ICNs is determined by the lengths of the links needed to support the communication patterns. Thus the mesh seems to perform the best amongst the three topologies(Mesh, Torus and Folded Torus) considered in case studies. The effects of communication overheads on performance, power and energy of a multiprocessor chip using L1,L2 cache sizes as primary exploration parameters using accurate interconnect, processor, on-chip and off-chip memory modelling are presented. On-chip and off-chip communication times have significant impact on execution time and the energy efficiency of CMPs. Large cache simply larger tile area that result in longer inter-tile communication link lengths and latencies, thus adversely impacting communication time. Smaller caches potentially have higher number of misses and frequent of off-tile communication. Energy efficient tile design is a configuration exploration and trade-off study using different cache sizes and tile areas to identify a power-performance optimal configuration for the CMP. Trade-offs are explored using a detailed, cycle accurate, multicore simulation frame-work which includes superscalar processor cores, cache coherent memory hierarchies, on-chip point-to-point communication networks and detailed interconnect model including pipelining and latency. Sapphire, a detailed multiprocessor execution environment integrating SESC, Ruby and DRAM Sim was used to run applications from the Splash2 benchmark(64KpointFFT).Link latencies are estimated for a16 core CMP simulation on Sapphire. Each tile has a single processor, L1 and L2 caches and a router. Different sizesofL1 andL2lead to different tile clock speeds, tile miss rates and tile area and hence interconnect latency. Simulations across various L1, L2 sizes indicate that the tile configuration that maximizes energy efficiency is related to minimizing communication time. Experiments also indicate different optimal tile configurations for performance, energy and energy efficiency. Clustered interconnection network, communication aware cache bank mapping and thread mapping to physical cores are also explored as potential energy saving solutions. Results indicate that ignoring link latencies can lead to large errors in estimates of program completion times, of up to 17%. Performance optimal configurations are achieved at lower L1 caches and at moderateL2 cache sizes due to higher operating frequencies and smaller link lengths and comparatively lesser communication. Using minimal L1 cache size to operate at the highest frequency may not always be the performance-power optimal choice. Larger L1 sizes, despite a drop in frequency, offer a energy advantage due to lesser communication due to misses. Clustered tile placement experiments for FFT show considerable performance per watt improvement (1.2%). Remapping most accessed L2 banks by a process in the same core or neighbouring cores after communication traffic analysis offers power and performance advantages. Remapped processes and banks in clustered tile placement show a performance per watt improvement of5.25% and energy reductionof2.53%. This suggests that processors could execute a program in multiple modes, for example, minimum energy, maximum performance.

Des modèles de chimie transport permettent le suivi réaliste des polluants en phase gazeuse dans l'atmosphère. Cependant, lapollution atmosphérique se trouve aussi sous forme de fines particules en suspension, les aérosols, qui interagissent avec la phase gazeuse, le rayonnement solaire, et possèdent une dynamique propre. Cette thèse a pour objet la modélisation et la simulation numérique de l'Equation Générale de la Dynamique des aérosols (GDE). La partie I traite de quelques points théoriques de la modélisation des aérosols. La partie II est consacrée à l'élaboration du module d'aérosols résolu en taille (SIREAM). dans la partie III, on effectue la réduction du modèle en vue de son utilisation dans un modèle de dispersion tel que POLAIR3D. Plusieurs points de modélisation restent encore largement ouverts: la partie organique des aérosols, le mélange externe, le couplage à la turbulence, et les nano-particules.