The purpose of this thesis is to present methods for visibility determination and to design and implement an application to demonstrate visibility determination in a 3D maze.

Data orientation is a common design principle in distributed data management systems. In contrast to process-oriented or transaction-oriented system designs, data-oriented architectures are based on data locality and function shipping. The tight coupling of data and processing thereon is implemented in different systems in a variety of application scenarios such as data analysis, database-as-a-service, and data management on multiprocessor systems. Data-oriented systems, i.e., systems that implement a data-oriented architecture, bundle data and operations together in tasks which are processed locally on the nodes of the distributed system. Allocation strategies, i.e., methods that decide the mapping from tasks to nodes, are core components in data-oriented systems. Good allocation strategies can lead to balanced systems while bad allocation strategies cause skew in the load and therefore suboptimal application performance and infrastructure utilization. Optimal allocation strategies are hard to find given the complexity of the systems, the complicated interactions of tasks, and the huge solution space. To ensure the scalability of data-oriented systems and to keep them manageable with hundreds of thousands of tasks, thousands of nodes, and dynamic workloads, fast and reliable allocation strategies are mandatory. In this thesis, we develop novel allocation strategies for data-oriented systems based on graph partitioning algorithms. Therefore, we show that systems from different application scenarios with different abstraction levels can be generalized to generic infrastructure and workload descriptions. We use weighted graph representations to model infrastructures with bounded and unbounded, i.e., overcommited, resources and possibly non-linear performance characteristics. Based on our generalized infrastructure and workload model, we formalize the allocation problem, which seeks valid and balanced allocations that minimize communication. Our allocation strategies partition the workload graph using solution heuristics that work with single and multiple vertex weights. Novel extensions to these solution heuristics can be used to balance penalized and secondary graph partition weights. These extensions enable the allocation strategies to handle infrastructures with non-linear performance behavior. On top of the basic algorithms, we propose methods to incorporate heterogeneous infrastructures and to react to changing workloads and infrastructures by incrementally updating the partitioning. We evaluate all components of our allocation strategy algorithms and show their applicability and scalability with synthetic workload graphs. In end-to-end--performance experiments in two actual data-oriented systems, a database-as-a-service system and a database management system for multiprocessor systems, we prove that our allocation strategies outperform alternative state-of-the-art methods.

Parallelization of logic simulation on register-transfer and gate level is a promising way to accelerate extremely time-extensive system simulation processes during the design of whole processor structures. The background of this paper is given by the functional simulator parallelTEXSIM realizing simulation based on the clock-cycle algorithm over loosely-coupled parallel processor systems. In preparation for parallel cycle simulation, partitioning of hardware models is necessary, which essentially determines the efficiency of the following simulation. We introduce a new method of parameterized partition valuation for use within model partitioning algorithms. It is based on a formal definition of parallel cycle simulation involving a model of parallel computation called Communicating Processors. Parameters within the valuation function permit consideration of specific properties related to both the simulation target architecture and the hardware design to be simulated. Our partition valuation method allows performance estimation with respect to corresponding parallel simulation. This has been confirmed by tests concerning several models of real processors as, for instance, the PowerPC 604 with parallel simulation running on an IBM SP2.

The partitioning of complex processor models on the gate and register-transfer level for parallel functional simulation based on the clock-cycle algorithm is considered. We introduce a hierarchical partitioning scheme combining various partitioning algorithms in the frame of a competing strategy. Melting together different partitioning results within one level using superpositions we crossover to a mixture of experts one. This approach is improved applying genetic algorithms. In addition we present two new partitioning algorithms both of them taking cones as fundamental units for building partitions.

Abstract The topography of the Milešov part of the České středohoří Mts represents a suitable model for study of spatial distribution of diversity and the effects of ecological factors on species diversity and composition. Near-natural forest vegetation was sampled at eleven hills by stratified-randomly sited relevés. Soil samples were collected in relevés at nine hills also. The soil samples were used for maximal capillary capability, pH, carbon and nitrogen volume analyses. These ecological factors, as well as tree cover, altitude and heat load index, were used for examination of the correlation of ecological factors with diversity, species richness and species composition. Positive relationship between species richness and heat load index and soil reaction was identified. Species diversity (Shannon index) positively correlates with soil reaction also. After partialling out geographic components in the samples, a significant correlation between the heat load index, tree cover and altitude and species composition of the herb and shrub layer was found. Values of alpha and beta components were rated using partitioning of diversity to alpha and beta components at four levels (relevé - aspect - hill - landscape). The beta component at the aspect level and the beta component at the hill level were...

Two peccary species, Mylohyus elmorei and Prosthennops serus are described from the medium-bodied fauna of the Gray Fossil Site (GFS) of northeastern Tennessee. This site, recognized as an oak-hickory forest, is latest Hemphillian or earliest Blancan based on mammalian biochronology, with an estimated age of 4.9-4.5 Ma. The GFS represents the only site outside the Palmetto Fauna of Florida with M. elmorei, greatly expanding the species range north over 920 km, well into the Appalachian region. This is also the first Appalachian occurrence of the relatively widespread P. serus. Our understanding of intraspecific variation for both M. elmorei and P. serus is expanded due to morphological and proportional differences found in cranial and dental material from the GFS, Tyner Farm locality, Palmetto Fauna, and within the literature. The GFS M. elmorei material represents the most complete mandible and second cranium for the species, and preserve intraspecific variation in the length of the diastema, dental proportions, and the complexity of the cuspules of the hypoconulid complex. Similarly, mandibular material from the GFS for P. serus exhibited larger dentitions and a greater degree of robustness than currently recognized for the species.

Niche partitioning is a major component in understanding community ecology and how different species divide limited environmental resources, enabling them to coexist. Temporal niche partitioning has been widely studied in a broad sense, such as in species that forage on similar nutritional sources dividing activity along diurnal and nocturnal classifications. Here, we approach this temporal niche partitioning with higher resolution to investigate partitioning between species within the same broad temporal and foraging niche. Two species of diurnal orb-weaving spiders (Araneae: Araneidae), Verrucosa arenata and Micrathena gracilis, both construct their orbs in spatially similar locations throughout the understory of deciduous forests in the morning, forage on flying insects throughout the day, and retreat in the evening. However, despite consisting of what appear to be roughly similar total lengths of adhesive silk in the capture spiral, overall orb structure is starkly different: V. arenata orbs are relatively large in diameter and sparse with capture threads; M. gracilis orbs, condensed in diameter and tightly coiled. What other differences might distinguish foraging strategy within this same niche? With extensive observation in their natural environment, we have found that these two species employ two distinct strategies by modulating behavior and orb structure: V. arenata construct orbs earlier in the day, resulting in a longer foraging period. However, V. arenata webs are more likely to be destroyed during the day such that there is a higher variance in foraging duration in V. arenata. We also found that V. arenata actively capture and consume more large prey and that M. gracilis more passively capture and consume small prey more reliably. These data suggest that these species have evolved different foraging strategies with V. arenata being risk-prone and M. gracilis being risk-averse. This study provides a more nuanced analysis of niche partitioning between species occupying otherwise similar temporal, habitat, and foraging niches.

The fuel consumption of a seagoing vessel is, through a combination of Box-Cox transforms and principal component analysis, reduced to a univariatefunction of the primary principle component with mean model error −3.2%and error standard deviation 10.3%. In the process, a Latin-hypercube-inspired space partitioning sampling technique is developed and successfully used to produce a representative sampleused in determining the regression coefficients. Finally, a formal optimisation problem for minimising the fuel use is described. The problem is derived from a parametrised expression for the fuel consumption, and has only 3, or 2 if simplified, free variables at each timestep. Some information has been redacted in order to comply with NDA restrictions. Most redactions are either names (of vessels or otherwise), units, andin some cases (especially on figures) quantities. / <p>Presentation was performed remotely using Zoom.</p>

Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]... / The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....

Indiana University-Purdue University Indianapolis (IUPUI) / While optimization techniques have been studied since 300 B.C. when Euclid first considered the minimal distance between a point and a line, it wasn’t until 1966 that location optimization was first applied to a problem in healthcare. Location optimization techniques are capable of increasing efficiency and equity in the placement of many types of services, including those within the healthcare industry, thus enhancing quality of life. Medical imaging is a healthcare service which helps to determine medical diagnoses in acute and preventive care settings. It provides physicians with information guiding treatment and returning a patient back to optimal health. In this study, a retrospective analysis of the locations of current medical imaging centers in central Indiana is performed, and alternate placement as determined using optimization techniques is considered and compared. This study focuses on reducing the drive time experienced by the population within the study area to their nearest imaging facility. Location optimization models such as the P-Median model, the Maximum Covering model, and Clustering and Partitioning are often used in the field of operations research to solve location problems, but are lesser known within the discipline of Geographic Information Science. This study was intended to demonstrate the capabilities of these powerful algorithms and to increase understanding of how they may be applied to problems within healthcare. While the P-Median model is effective at reducing the overall drive time for a given network set, individuals within the network may experience lengthy drive times. The results further indicate that while the Maximum Covering model is more equitable than the P-Median model, it produces large sets of assigned individuals overwhelming the capacity of one imaging center. Finally, the Clustering and Partitioning method is effective at limiting the number of individuals assigned to a given imaging center, but it does not provide information regarding average drive time for those individuals. In the end, it is determined that a capacitated Maximal Covering model would be the preferred method for solving this particular location problem.