Scheduling dynamic dataflow graphs with model checking

With the shift towards many-core computer architectures, dataflow programming has been proposed as one potential solution for producing software that scales to a varying number of processor cores. Programming for parallel architectures is considered difficult as the current popular programming languages are inherently sequential and introducing parallelism is typically up to the programmer. Dataflow, however, is inherently parallel, describing an application as a directed graph, where nodes represent calculations and edges represent a data dependency in form of a queue. These queues are the only allowed communication between the nodes, making the dependencies between the nodes explicit and thereby also the parallelism. Once a node have the su cient inputs available, the node can, independently of any other node, perform calculations, consume inputs, and produce outputs. Data ow models have existed for several decades and have become popular for describing signal processing applications as the graph representation is a very natural representation within this eld. Digital lters are typically described with boxes and arrows also in textbooks. Data ow is also becoming more interesting in other domains, and in principle, any application working on an information stream ts the dataflow paradigm. Such applications are, among others, network protocols, cryptography, and multimedia applications. As an example, the MPEG group standardized a dataflow language called RVC-CAL to be use within reconfigurable video coding. Describing a video coder as a data ow network instead of with conventional programming languages, makes the coder more readable as it describes how the video dataflows through the different coding tools. While dataflow provides an intuitive representation for many applications, it also introduces some new problems that need to be solved in order for data ow to be more widely used. The explicit parallelism of a dataflow program is descriptive and enables an improved utilization of available processing units, however, the independent nodes also implies that some kind of scheduling is required. The need for efficient scheduling becomes even more evident when the number of nodes is larger than the number of processing units and several nodes are running concurrently on one processor core. There exist several data ow models of computation, with different trade-offs between expressiveness and analyzability. These vary from rather restricted but statically schedulable, with minimal scheduling overhead, to dynamic where each ring requires a ring rule to evaluated. The model used in this work, namely RVC-CAL, is a very expressive language, and in the general case it requires dynamic scheduling, however, the strong encapsulation of dataflow nodes enables analysis and the scheduling overhead can be reduced by using quasi-static, or piecewise static, scheduling techniques. The scheduling problem is concerned with nding the few scheduling decisions that must be run-time, while most decisions are pre-calculated. The result is then an, as small as possible, set of static schedules that are dynamically scheduled. To identify these dynamic decisions and to find the concrete schedules, this thesis shows how quasi-static scheduling can be represented as a model checking problem. This involves identifying the relevant information to generate a minimal but complete model to be used for model checking. The model must describe everything that may affect scheduling of the application while omitting everything else in order to avoid state space explosion. This kind of simplification is necessary to make the state space analysis feasible. For the model checker to nd the actual schedules, a set of scheduling strategies are de ned which are able to produce quasi-static schedulers for a wide range of applications. The results of this work show that actor composition with quasi-static scheduling can be used to transform data ow programs to t many different computer architecture with different type and number of cores. This in turn, enables dataflow to provide a more platform independent representation as one application can be fitted to a specific processor architecture without changing the actual program representation. Instead, the program representation is in the context of design space exploration optimized by the development tools to fit the target platform. This work focuses on representing the dataflow scheduling problem as a model checking problem and is implemented as part of a compiler infrastructure. The thesis also presents experimental results as evidence of the usefulness of the approach.

Cyanobacterial occurrence and detection of microcystin by planar chromatography in surface water of Billings and Guarapiranga Reservoirs, SP, Brazil

Billings and Guarapiranga Reservoirs were deeply affected by environmental disturbances, which more evident consequence are the cyanobacterial blooms. Microcystins are the most common cyanotoxin in freshwaters and more than 70 types are known. Different methods for microcystins analysis in water can be used, among which ELISA and HPLC are the most frequently employed. However, less sophisticated and more economic methods can also be used. This is the case of planar chromatography (thin-layer chromatography) method previously used in cyanotoxins purification but gradually replaced by others. Posterior optimization of the microcystin chromatography conditions and because of its simplicity, rapidity, efficiency and low cost, this method is again considered an option for the analysis of microcystins and nodularins. Considering the importance of Billings and Guarapiranga Reservoirs for drinking water supplies and the few scientific data about cyanobacteria and cyanotoxins in these water bodies, the aims of this work are to analyze the biodiversity of cyanobacteria in the Billings and Guarapiranga Reservoirs and the detection of dissolved microcystins in the water. It was possible to identify 17 species of cyanobacteria, 9 of them being potentially toxic. In Billings Reservoir Microcystis aeruginosa (Kützing) Kützing and Cylindrospermopsis raciborskii (Woloszynska) Seenayya & Subba Raju are the most common species, while in Guarapiranga Reservoir only M. aeruginosa was considered as a common species. Microcystins were detected in all Billings Reservoir samples and in only one sample from Guarapiranga Reservoir.

Hygro-elasto-plastic behavior of planar orthotropic material

The mechanical and hygroscopic properties of paper and board are factors affecting the whole lifecycle of a product, including paper/board quality, production, converting, and material and energy savings. The progress of shrinkage profiles, loose edges of web, baggy web causing wrinkling and misregistration in printing are examples of factors affecting runnability and end product quality in the drying section and converting processes, where paper or board is treated as a moving web. The structural properties and internal stresses or plastic strain differences built up during production also cause the end-product defects related to distortion of the shape of the product such as sheet or box. The objective of this work was to construct a model capable of capturing the characteristic behavior of hygroscopic orthotropic material under moisture change, during different external in-plane stretch or stress conditions. Two independent experimental models were constructed: the elasto-plastic material model and the hygroexpansivity-shrinkage model. Both describe the structural properties of the sheet with a fiber orientation probability distribution, and both are functions of the dry solids content and fiber orientation anisotropy index. The anisotropy index, introduced in this work, simplifies the procedure of determining the constitutive parameters of the material model and the hygroexpansion coefficients in different in-plane directions of the orthotropic sheet. The mathematically consistent elasto-plastic material model and the dry solids content dependent hygroexpansivity have been constructed over the entire range from wet to dry. The presented elastoplastic and hygroexpansivity-shrinkage models can be used in an analytical approach to estimate the plastic strain and shrinkage in simple one-dimensional cases. For studies of the combined and more complicated effects of hygro-elasto-plastic behavior, both models were implemented in a finite element program for a numerical solution. The finite element approach also offered possibilities for studying different structural variations of orthotropic planar material, as well as local buckling behavior and internal stress situations of the sheet or web generated by local strain differences. A comparison of the simulation examples presented in this work to results published earlier confirms that the hygro-elasto-plastic model provides at least qualitatively reasonable estimates. The application potential of the hygro-elasto-plastic model is versatile, including several phenomena and defects appearing in the drying, converting and end-use conditions of the paper or board webs and products, or in other corresponding complex planar materials.

Methodological approaches to planar and volumetric scintigraphic imaging of small volume targets with high spatial resolution and sensitivity

Single-photon emission computed tomography (SPECT) is a non-invasive imaging technique, which provides information reporting the functional states of tissues. SPECT imaging has been used as a diagnostic tool in several human disorders and can be used in animal models of diseases for physiopathological, genomic and drug discovery studies. However, most of the experimental models used in research involve rodents, which are at least one order of magnitude smaller in linear dimensions than man. Consequently, images of targets obtained with conventional gamma-cameras and collimators have poor spatial resolution and statistical quality. We review the methodological approaches developed in recent years in order to obtain images of small targets with good spatial resolution and sensitivity. Multipinhole, coded mask- and slit-based collimators are presented as alternative approaches to improve image quality. In combination with appropriate decoding algorithms, these collimators permit a significant reduction of the time needed to register the projections used to make 3-D representations of the volumetric distribution of target’s radiotracers. Simultaneously, they can be used to minimize artifacts and blurring arising when single pinhole collimators are used. Representation images are presented, which illustrate the use of these collimators. We also comment on the use of coded masks to attain tomographic resolution with a single projection, as discussed by some investigators since their introduction to obtain near-field images. We conclude this review by showing that the use of appropriate hardware and software tools adapted to conventional gamma-cameras can be of great help in obtaining relevant functional information in experiments using small animals.

Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Rings, Group Rings, and Their Graphs

We associate some graphs to a ring R and we investigate the interplay between the ring-theoretic properties of R and the graph-theoretic properties of the graphs associated to R. Let Z(R) be the set of zero-divisors of R. We define an undirected graph ᴦ(R) with nonzero zero-divisors as vertices and distinct vertices x and y are adjacent if xy=0 or yx=0. We investigate the Isomorphism Problem for zero-divisor graphs of group rings RG. Let Sk denote the sphere with k handles, where k is a non-negative integer, that is, Sk is an oriented surface of genus k. The genus of a graph is the minimal integer n such that the graph can be embedded in Sn. The annihilating-ideal graph of R is defined as the graph AG(R) with the set of ideals with nonzero annihilators as vertex such that two distinct vertices I and J are adjacent if IJ=(0). We characterize Artinian rings whose annihilating-ideal graphs have finite genus. Finally, we extend the definition of the annihilating-ideal graph to non-commutative rings.

Planar Topological Defects in Unconventional Superconductors

In this work, we consider the properties of planar topological defects in unconventional superconductors. Specifically, we calculate microscopically the interaction energy of domain walls separating degenerate ground states in a chiral p-wave fermionic superfluid. The interaction is mediated by the quasiparticles experiencing Andreev scattering at the domain walls. As a by-product, we derive a useful general expression for the free energy of an arbitrary nonuniform texture of the order parameter in terms of the quasiparticle scattering matrix. The thesis is structured as follows. We begin with a historical review of the theories of superconductivity (Sec. 1.1), which led the way to the celebrated Bardeen-Cooper- Schrieffer (BCS) theory (Sec. 1.3). Then we proceed to the treatment of superconductors with so-called "unconventional pairing" in Sec. 1.4, and in Sec. 1.5 we introduce the specific case of chiral p-wave superconductivity. After introducing in Sec. 2 the domain wall (DW) model that will be considered throughout the work, we derive the Bogoliubov-de Gennes (BdG) equations in Sec. 3.1, which determine the quasiparticle excitation spectrum for a nonuniform superconductor. In this work, we use the semiclassical (Andreev) approximation, and solve the Andreev equations (which are a particular case of the BdG equations) in Sec. 4 to determine the quasiparticle spectrum for both the single- and two-DW textures. The Andreev equations are derived in Sec. 3.2, and the formal properties of the Andreev scattering coefficients are discussed in the following subsection. In Sec. 5, we use the transfer matrix method to relate the interaction energy of the DWs to the scattering matrix of the Bogoliubov quasiparticles. This facilitates the derivation of an analytical expression for the interaction energy between the two DWs in Sec. 5.3. Finally, to illustrate the general applicability our method, we apply it in Sec. 6 to the interaction between phase solitons in a two-band s-wave superconductor.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Diastereoselective Synthesis of Planar Chiral N-Substituted Ferrocenes Derived from Epimeric Imidazolones and their Application to Asymmetric Hydrogenation of Quinolines

This thesis describes the synthesis and use of an N-substituted ferrocene bearing a proline-derived chiral directing group and diastereoselective lithiation-electrophile quench of the pro-Sp hydrogen of the ferrocene to give planar chiral products in >95:5 dr. The auxiliary group is found to be stable to lithium bases of types RLi and R2NLi giving the same diastereoselectivity. The anti- epimer of the previously mentioned syn auxiliary induces lithiation of pro Rp rather than pro Sp hydrogen in >95:5 dr. Upon electrophile quench and elimination, the enantiomer of the syn-derived planar chiral imidazolone is obtained. Hence, this method provides a practical way to prepare planar chiral enantiomers in this series without the use of a more expensive D-proline derived starting material. The syn and anti epimers have β, γ-stereogenic centers and the origin of stereoselectivity in lithiation appears to be driven by the conformational bias exerted by the β-silyloxy moiety in each chiral auxiliary. In the thesis, this conclusion is supported using insensitivity of lithiation selectivity to the bulkiness of the base, comparison of enantiomers, deuteration experiments, nOe difference studies and computational modeling of the ground states and lithiation transition states for both substrates. The products are then converted to ligand precursors to make iridium and rhodium complexes. Among them, one of the cationic iridium complex is found to be effective in the asymmetric hydrogenation of 2-substituted quinolines with enantioselectivities up to 80% at pressures as low as 5 atm.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Diagrams (charts and graphs) made into a booklet with a newspaper cover

Diagrams (charts and graphs) made into a booklet with a newspaper cover. This booklet contains cross sections of the back ditch on the south side of the Welland Canal feeder, west of the Marshville culverts (45 pages, hand drawn). This was created by Fred Holmes, Oct. 3, 1857.