Worst Case Execution Time (WCET) is an important metric for programs running on real-time systems, and finding precise estimates of a program’s WCET is crucial to avoid over-allocation and wastage of hardware resources and to improve the schedulability of task sets. Hardware Caches have a major impact on a program’s execution time, and accurate estimation of a program’s cache behavior generally leads to significant reduction of its estimated WCET. However, the cache behavior of an access cannot be determined in isolation, since it depends on the access history, and in multi-path programs, the sequence of accesses made to the cache is not fixed. Hence, the same access can exhibit different cache behavior in different execution instances. This issue is further exacerbated in shared caches in a multi-core architecture, where interfering accesses from co-running programs on other cores can arrive at any time and modify the cache state. Further, cache analysis aimed towards WCET estimation should be provably safe, in that the estimated WCET should always exceed the actual execution time across all execution instances. Faced with such contradicting requirements, previous approaches to cache analysis try to find memory accesses in a program which are guaranteed to hit the cache, irrespective of the program input, or the interferences from other co-running programs in case of a shared cache. To do so, they find the worst-case cache behavior for every individual memory access, analyzing the program (and interferences to a shared cache) to find whether there are execution instances where an access can super a cache miss. However, this approach loses out in making more precise predictions of private cache behavior which can be safely used for WCET estimation, and is significantly imprecise for shared cache analysis, where it is often impossible to guarantee that an access always hits the cache. In this work, we take a fundamentally different approach to cache analysis, by (1) trying to find worst-case behavior of groups of cache accesses, and (2) trying to find the exact cache behavior in the worst-case program execution instance, which is the execution instance with the maximum execution time. For shared caches, we propose the Worst Case Interference Placement (WCIP) technique, which finds the worst-case timing of interfering accesses that would cause the maximum number of cache misses on the worst case execution path of the program. We first use Integer Linear Programming (ILP) to find an exact solution to the WCIP problem. However, this approach does not scale well for large programs, and so we investigate the WCIP problem in detail and prove that it is NP-Hard. In the process, we discover that the source of hardness of the WCIP problem lies in finding the worst case execution path which would exhibit the maximum execution time in the presence of interferences. We use this observation to propose an approximate algorithm for performing WCIP, which bypasses the hard problem of finding the worst case execution path by simply assuming that all cache accesses made by the program occur on a single path. This allows us to use a simple greedy algorithm to distribute the interfering accesses by choosing those cache accesses which could be most affected by interferences. The greedy algorithm also guarantees that the increase in WCET due to interferences is linear in the number of interferences. Experimentally, we show that WCIP provides substantial precision improvement in the final WCET over previous approaches to shared cache analysis, and the approximate algorithm almost matches the precision of the ILP-based approach, while being considerably faster. For private caches, we discover multiple scenarios where hit-miss predictions made by traditional Abstract Interpretation-based approaches are not sufficient to fully capture cache behavior for WCET estimation. We introduce the concept of cache miss paths, which are abstractions of program path along which an access can super a cache miss. We propose an ILP-based approach which uses cache miss paths to find the exact cache behavior in the worst-case execution instance of the program. However, the ILP-based approach needs information about the worst-case execution path to predict the cache behavior, and hence it is difficult to integrate it with other micro-architectural analysis. We then show that most of the precision improvement of the ILP-based approach can be recovered without any knowledge of the worst-case execution path, by a careful analysis of the cache miss paths themselves. In particular, we can use cache miss paths to find the worst-case behavior of groups of cache accesses. Further, we can find upper bounds on the maximum number of times that cache accesses inside loops can exhibit worst-case behavior. This results in a scalable, precise method for performing private cache analysis which can be easily integrated with other micro-architectural analysis.

Please read the abstract in the section, 00front, of this document / Thesis (DPhil)--University of Pretoria, 2008. / Civil Engineering / unrestricted

[pt] O fenômeno de estabilidade de tensão é um problema associado ao fluxo de potência ativa e reativa nas linhas de transmissão. A manifestação mais conhecida do fenômeno é a existência de uma máxima carga que pode ser alimentada pela rede, mas, atualmente também se sabe da existência de uma máxima injeção de potência ativa e reativa na rede por geradores e compensadores. É apresentado um método para avaliar as condições de carregamento da rede e detectar barras críticas. Identifica-se a sub-rede utilizada para transmitir potência ativa de ou para a barra critica, determinam-se os caminhos de transmissão que a compõem e identifica-se o ramo crítico do caminho mais carregado. É o ramo a ter seu fluxo de potência diminuído. Nesta dissertação foi proposta a determinação da sub-rede quando a barra em análise é de tensão controlada por compensador. Além disso, foram propostas modificações no método existente: injeção de potência ao invés de admitância equivalente no isolamento da sub-rede e dos caminhos de transmissão, e índices de estabilidade ao invés de fórmulas analíticas na determinação do caminho mais carregado e do ramo crítico. / [en] The voltage stability phenomenon is a problem related with the flow of active and reactive power in transmission lines. The main characteristic of this phenomenon is the existence of a maximum load that can be supplied by the network, but actually it is also known the existence of a maximum active and reactive power injection at the network supplied by generators and compensators. In this dissertation, a method is presented to evaluate the conditions of the network loadability and the critical buses identification. The network used to transmit the active power from or to a critical bus and its transmissions lines are identified, and identify the critical branch of the most loaded transmission path. This critical branch will have its power flow reduced. In this dissertation, is proposed the determination of the sub-transmission network when the bus under analysis has its voltage controlled by compensator. Furthermore, were proposed modifications to the current method: power injection rather than equivalent admittance in isolation of the sub-transmission network and the transmission paths and also, using voltage stability indexes rather than using analytical formulas to determine the most loaded path and critical branch.

En 2008, la Banque mondiale a consacré son « rapport annuel sur le développement » à l'agriculture. Cela n’avait plus été le cas depuis 25 ans. Elle y montre que la croissance agricole est plus efficace que celle d’autres secteurs pour réduire la pauvreté. La productivité du travail agricole des actifs agricoles y est paradoxalement à peine citée : ses facteurs explicatifs de court terme comme ses variables structurantes sur le long terme ne sont pas analysés. Cette thèse entend contribuer à une meilleure compréhension des relations dynamiques qu’entretiennent la démographie et le développement non agricole avec le développement agricole (élévation de la productivité du travail agricole). Sous quelles conditions démo-économiques la transformation structurelle d'une économie (baisse du poids relatif du secteur agricole dans l’économie (actifs et valeur ajoutée)) peut-elle s'accompagner d'un développement agricole ? Alors qu’un secteur industriel ou tertiaire qui se développe est généralement attracteur d’actifs, une loi inverse existe-t-elle pour le secteur agricole ? Celui-ci doit-il nécessairement se vider de ses actifs pour se développer ? Y’a-t-il jamais eu, et peut-il y avoir développement agricole dans un contexte de croissance continue du nombre des actifs agricoles ?Notre (hypo)thèse principale est que la combinaison dynamique des facteurs «terre » et «actif agricole », dont la résultante est la « surface travaillée par actif agricole », est la véritable clé du développement agricole, davantage que la productivité de la terre. Nous analysons les déterminants des niveaux et taux de croissance de la productivité du travail agricole au cours de la période 1980 - 2007, à différentes échelles géographiques. Une attention particulière est mise sur la variable « nombre d’actifs agricoles », à l'aide de différents jeux de données (internationales, nationales, données d’enquêtes de terrain), à différentes échelles (monde, Mexique, 31 états fédérés et 2400 Municipes mexicains) et avec diverses méthodes (décomposition factorielle, cartes, classifications ascendantes hiérarchiques, inférence statistique, enquêtes de terrain auprès de ménages agricoles, non agricoles, d’institutions). Au niveau mondial, nous mettons en évidence une « course de vitesse » entre actifs agricoles et terre dans certaines régions du monde et proposons le concept de «transition agricole démographique » ainsi que sa typologie associée. Le Mexique est ensuite choisi pour ses agricultures présentant des niveaux de développement très contrastés, en synchronie comme en diachronie. Nous cherchons à expliquer les différences de trajectoires de développement agricole observées au Mexique. Nous analysons l’influence de variables caractérisant l’économie non agricole, la substitution du capital machine au travail, la libéralisation foncière, la géographie (physique et humaine). Dans les comparaisons internationales comme au Mexique, nous montrons que le taux de croissance de la surface par actif agricole a une influence marginale plus forte sur le taux de croissance de la productivité du travail agricole, que le taux de croissance de la productivité de la terre. Enfin, nous analysons les stratégies économiques de ménages et actifs agricoles, du Municipe de Teopisca dans la région de Los Altos de Chiapas, « piégés » dans un contexte de « transition agricole démographique bloquée » (décroissance tendancielle de la surface travaillée par actif) : diversification des sources de revenus (vers le non agricole) et tentatives d’élévation de la productivité de la terre sont les deux principales stratégies déployées sous contraintes de défaillances des marchés (travail, crédit) et d’accès à l’eau d’irrigation. / In 2008, the World Bank has dedicated its "Annual Report on Development" to agriculture. This had not been the case for 25 years. It shows that agricultural growth is more effective than other sectors to reduce poverty. The agricultural labor productivity of the agricultural workforce is paradoxically barely mentioned: its explanatory factors for the short term as its structural variables in the long term are not analyzed. This thesis aims to contribute to a better understanding of the dynamic relationship between demography and non-agricultural development with agricultural development (increased productivity of agricultural labor). Under what demo-economic conditions can the structural transformation of an economy (i.e. the decline in the relative weight of the agricultural sector in the economy (workers and value added)) be accompanied by agricultural development? While an industrial or service sector that develops generally attracts workers, is there an opposite relationship in the agricultural sector? Does the agricultural sector have to lose its workers to develop? Has an agricultural sector ever developed in a context of continuous growth in the number of agricultural workers? Our main (hypo)thesis is that the dynamic combination of factors « land » and « agricultural worker », whose resultant is the « agricultural area worked per agricultural worker », is the real key to agricultural development, more than the productivity of the land.We analyze the determinants of the level and of the growth rate of the agricultural labor productivity over the 1980-2007 period, at different geographical levels. Special focus is put on the evolution of the « number of agricultural workers », using different sets of data (international, national, field surveys data), at different scales (world, Mexico, and 31 federal states 2400 Mexican municipalities) and with various methods (factor decomposition, maps, hierarchical ascending classifications, statistical inference, field surveys of farming households).Globally, we highlight a « race » between land and the number of agricultural workers in certain regions of the world and propose the concept of « demographic transition agriculture » and its associated typology.Mexico is then chosen for its agriculture showing very contrasting levels of development, for both synchronic and diachronic observation. We seek to understand the differences in agricultural development paths observed in Mexico by analyzing the influence of variables characterizing the non-farm economy, the substitution of machinery capital for labor, land liberalization, geography (physical and human).In international comparisons as within Mexico, we show that the growth rate of the area by agricultural worker has a marginally stronger influence on the growth rate of agricultural labor productivity, than the growth rate of land productivity.Finally, in the Municipality of Teopisca in the Los Altos region of Chiapas, we analyze the economic strategies of farm households « trapped » in a context of « blocked demographic agricultural transition » (downward trend of the agricultural area per worker): income diversification (toward the non-agricultural sector) and attempts to rise the land productivity are the two main strategies deployed under local severe constraints of market failures (labor, credit) and difficult access to irrigation water.

The aim and object is to undergo analysis of bicycle trails in terms of their qualifications within time and technical aspects, creation of SWOT analysis, evaluating strengths and weaknesses, threats and opportunities of bicycle trails, exploration and financing, looks at the development of bicycle trailsin Olomouc because of the focus on practical part of the project of the biking trails located in this area. In the practical part of the project the biking trails are evaluated according to cost-benefit analysis method using CBA SW eCBA where all the necessary characteristics of cycle paths and their identification and quantification in terms of financial and economic analysis of the project is described. The outcome of this project is to evaluate the methodology for dou-term sustainability. Finally, the evaluation of cycle paths as a stimulus for development of area.

Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB. / Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.

Das Transport- und Relaxationsverhalten verschiedener Quantenmodelle wird untersucht. Den ersten Teil der vorliegenden Arbeit bildet die Untersuchung der Transporteigenschaften von speziellen finiten modularen Quantensystemen bzgl. einer Boltzmann-Gleichung (BG). Diese Systeme, in denen unter bestimmten Bedingungen diffusiver Transport beobachtet werden kann, wurden mit verschiedenen Methoden zur Beschreibung von Quantentransport untersucht. Dabei zeigt sich, dass sich das diffusive Transportverhalten in diesen Systemen aus der zugrunde liegenden Schrödinger Dynamik heraus beschreiben lässt. Ob die diffusive Dynamik in diesen Systemen ebenfalls auf der Basis einer BG beschrieben werden kann, wird analytisch und numerisch untersucht. Im zweiten Teil wird die Relaxationsdynamik in quantenmechanischen Vielteilchensystemen untersucht. Speziell wird versucht, die Lebensdauern von angeregten Elektronen (Löchern) in Metallen, welche mit dem Fermi-See der Elektronen wechselwirken, mittels der zeitfaltungsfreien Projektionsoperator-Methode (TCL) zu bestimmen. Letztere liefert einen analytischen Ausdruck für die Dämpfungsrate (inverse Lebensdauer), welche temperaturabhängig ist und im Rahmen von Standard-Streuprozessen interpretiert werden kann. Um dieses analytische Ergebnis zu testen, wird es angewendet, um die Lebensdauern angeregter Elektronen (Löcher) in Aluminium zu bestimmen, für das ein Jellium Modell verwendet wird. Die Ergebnisse, die man über Monte-Carlo-Integration erhält, werden mit experimentellen und theoretischen Daten aus Selbstenergie-Rechnungen verglichen. Des Weiteren werden die Lebensdauern angeregter Elektronen in Kupfer ermittelt, für das ein Tight-Binding-Modell verwendet wird.

This study contributes towards the ever-growing research field of sustainability reporting within the broader context of integrated reporting. Sustainability reporting is the integration of the environmental, social and economic aspects of an organisation in the communication with stakeholders. South Africa’s Johannesburg Stock Exchange (JSE) has taken a leading role in the drive for integrated reporting. The aim of the study was to determine the quality of sustainability reporting for the JSE listed firms post the introduction of listing requirements for integrated reporting. Reports of good quality enable stakeholders to make sound decisions from the reported information. The study was limited to sustainability reporting for JSE listed firms. The theoretical lens for the study is the stakeholder theory developed by Freeman (1984). The study analyses perceptions of sustainability practitioners on quality of sustainability reporting for JSE listed firms for the period of 2009 to 2017. In this study, the focus was to gain rich insights from sustainability practitioners involved in the sustainability reporting value chain of JSE listed firms. This included report preparers, report assurance providers, report users and other report critical reviewers. The recordings of the semistructured interviews undertaken in this study were transcribed verbatim and analysed using a descriptive analysis technique called Tesch’s coding. The researcher reviewed the information, probed and summarised the main themes that emerged from the qualitative research. The study shows that there are no explicit mandatory requirements for integrated reporting and sustainability reporting for JSE listed firms, contrary to the perception of some scholars and practitioners. The publication of integrated and sustainability reports is, however, now business best practice for firms on the JSE. Admittedly, this is partly because of King Codes recommendations of South Africa that promotes integrated reporting. Sustainability reporting has been improving over a nine-year period, but this cannot be solely attributed to the listing requirements. Basic interventions such as listing requirements for integrated reporting on the JSE and the shareholder compacts on South Africa’s State-owned companies, although not explicitly mandatory, have contributed in promoting integrated and sustainability reporting in South Africa. There are many drivers of sustainability reporting for JSE listed firms. These can be categorised as internal and external drivers. The internal drivers can also be regarded as critical success factors for sustainability reporting quality for JSE listed firms. The study revealed the dominance of the two drivers of sustainability reporting, namely stakeholder demands and the role of leadership in shaping sustainability reporting in the South African context. The combination of the two drivers on sustainability reporting for JSE listed firms confirms the assumptions of the stakeholder theory. In the process of determining the trends in reporting and the actual drivers for improved quality in reporting, the cross-cutting theme that emerged was that different organisations are in different stages of their reporting journey. There are early adopters and late adopters. Organisations that choose to be involved in integrated reporting and sustainability reporting experience a real journey of reporting, hence various organisations are at different stages depending when and how they commenced their reporting journey. The researcher coined that process “sustainability reporting life stages”. The study further found that there are many determinants for quality of sustainability reporting for JSE listed firms. The sustainability practitioners perceive quality from the view of the Global Reporting Initiative and Integrated Reporting Council frameworks, thus confirming the entrenchment of the two frameworks in the South African context. The best option assurance mechanism in the form of the Combined Assurance Model was observable in the better reporting sectors on the JSE and State-owned companies. The critical paths for sustainability reporting have been provided, indicating the need for sustainability leadership and stakeholder inclusiveness. / Business Management / D.B.L.

This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.

With the rapid adoption of cloud technologies, organizations have benefited from improved scalability, cost efficiency, and flexibility. However, this shift towards cloud computing has raised concerns about the safety and security of sensitive data and applications. Security engineers face significant challenges in protecting cloud environments due to their dynamic nature and complex infrastructures. Traditional security approaches, such as attack graphs that showcase attack vectors in given network topologies, often fall short of capturing the intricate relationships and dependencies of cloud environments. Knowledge graphs, essentially a knowledge base with a directed graph structure, are an alternative to attack graphs. They comprehensively represent contextual information such as network topology information and vulnerabilities, as well as the relationships between all of the entities. By leveraging knowledge graphs’ inherent flexibility and scalability, security engineers can gain deeper insights into the complex interconnections within cloud systems, enabling more effective threat analysis and mitigation strategies. This thesis involves the development of a new tool, HackerGraph, specifically designed to utilize knowledge graphs for cloud security. The tool integrates data from various other tools, gathering information about the cloud system’s architecture and its vulnerabilities and weaknesses. By analyzing and modeling the information using a knowledge graph, the tool provides a holistic view of the cloud ecosystem, identifying potential vulnerabilities, attack vectors, and areas of concern. The results are compared to modern stateof-the-art tools, both in the area of attack graphs and knowledge graphs, and we prove that more information and more attack paths in vulnerable by-design scenarios can be provided. We also discuss how this technology can evolve, to better handle the intricacies of cloud systems and help security engineers in fully protecting their complicated cloud systems. / Organisationers snabba anammande av molnteknologier har låtit dem dra nytta förbättrad skalbarhet, kostnadseffektivitet och flexibilitet. Däremot har detta skifte också lett till nya säkerhetsproblem, speciellt gällande applikationer och behandlingen av känslig information. Molnmiljöers dynamiska natur och komplexa problem skapar markanta problem för de säkerhetstekniker som ansvarar för att skydda miljön. Den typ av invecklade förhållanden som finns i molnet fångas däremot sällan av traditionella säkerhetsmetoder, såsom attackgrafer. Ett alternativ till attackgrafer är därför kunskapsgrafer som utförligt kan representera kontextuell information, förhållanden och domänspecifik kunskap. Genom kunskapsgrafernas naturliga flexibilitet och skalbarhet skulle säkerhetsteknikerna kunna få djupare insikter kring de komplexa förhållanden som råder i molnmiljöer för att på ett mer effektivt sätt analysera hot och hur de kan förebyggas. Det här arbetet involverar därför utvecklingen av ett nytt verktyg specifikt designat för att använda kunskapsgrafer, nämligen HackerGraph. Verktyget integrerar data från flera andra verktyg som samlar information om molnmiljöers arkitektur samt deras sårbarheter eller svagheter. Genom att analysera och modellera informationen som en kunskapsgraf skapar verktyget en holistisk bild av molnekosystemet som kan identifiera potentiella sårbarheter, attackvektorer eller andra problemområden. Resultaten jämförs sedan med moderna verktyg inom både attack- och kunskapsgrafer. Vi bevisar därmed både hur mer information och fler attackvägar kan tillhandahållas från scenarion som är sårbara per design. Vi diskuterar också hur den här teknologin kan utvecklas för att bättre hantera molnmiljöers komplexitet samt hur den kan hjälpa säkerhetstekniker att skydda sina komplicerade molnmiljöer.