Computer Science and Automation (CSA)https://etd.iisc.ac.in/handle/2005/172024-03-28T20:33:26Z2024-03-28T20:33:26Z2-Level Page Tables (2-LPT): A Building Block for Efficient Address Translation in Virtualized EnvironmentsBaviskar, Akshay Sureshhttps://etd.iisc.ac.in/handle/2005/56842022-05-04T09:08:02Z2-Level Page Tables (2-LPT): A Building Block for Efficient Address Translation in Virtualized Environments
Baviskar, Akshay Suresh
Efficient address translation mechanisms are gaining more and more attention as the virtual
address range of the processors keeps expanding and the demand for machine virtualization
increases with cloud and data center-based services. Traditional radix-tree based address translations
can incur significant overheads in big data applications, particularly under virtualization,
due to multi-level tree walks and nested translation. The overheads stem primarily from the
unnecessary generality — ability to support several hundreds of thousands of virtual memory
regions in the virtual address space — supported by current processors.
We observe that in the common case, however, a process’s virtual address space contains
only a few contiguously allocated sections, which can be efficiently translated using a shallow
tree with two levels. We propose such a compact structure, called 2-Level Page Table(2-LPT),
which serves as a key building block for address translation in virtualized environment. A key
advantage of 2-LPT is that it maintains two levels of page tables irrespective of the size of the
virtual address space. Translating a virtual address using 2-LPT is fast. A walk on a 2-LPT
requires up to two memory accesses. In practice, however, the root level table is well cached in
the Page Walk Caches, thus, single memory access is sufficient. Under native execution, 2-LPT
reduces the page walk latency by up to 20.9% (9.38% on average) and improves performance by
up to 10.1% (1.66% on average) over the conventional four-level radix tree page tables, on a set
of memory-intensive applications.
2-LPT is more beneficial under virtualization. A naive extension of 2-LPT reduces the cost
of nested page walk from 24 to 8 memory accesses. To achieve further reduction, we propose
two optimizations: (i) Enhanced Partial Shadow Paging (ePSP) which employs a limited form
of shadow paging for the root-level of 2-LPT, and (ii) Host PTE Mirroring (HPM) which
allows accessing the host page table entry without performing host page table walk. These
optimizations reduce the number of memory accesses to just one, on average, while avoiding slow
VM exits. 2-LPT speeds up applications by 5.6%-50.9% (24.6%, on average) over the baseline
nested page walks. Compared to the best performing state-of-the-art proposal, 2-LPT achieves
an average reduction of 41.5% and 15.7% in page walk latency and execution cycles
Access Path Based Dataflow Analysis For Sequential And Concurrent ProgramsArnab De, *https://etd.iisc.ac.in/handle/2005/25642022-04-12T05:31:28Z2016-09-14T00:00:00ZAccess Path Based Dataflow Analysis For Sequential And Concurrent Programs
Arnab De, *
In this thesis, we have developed a flow-sensitive data flow analysis framework for value set analyses for Java-like languages. Our analysis frame work is based on access paths—a variable followed by zero or more field accesses. We express our abstract states as maps from bounded access paths to abstract value sets. Using access paths instead of allocation sites enables us to perform strong updates on assignments to dynamically allocated memory locations. We also describe several optimizations to reduce the number of access paths that need to be tracked in our analysis. We have instantiated this frame work for flow-sensitive pointer and null-pointer analysis for Java. We have implemented our analysis inside the Chord frame work. A major part of our implementation is written declaratively using Datalog. We leverage the use of BDDs in Chord for keeping our memory usage low. We show that our analysis is much more precise and faster than traditional flow-sensitive and flow-insensitive pointer and null-pointer analysis for Java.
We further extend our access path based analysis frame work to concurrent Java programs. We use the synchronization structure of the programs to transfer abstract states from one thread to another. Therefore, we do not need to make conservative assumptions about reads or writes to shared memory. We prove our analysis to be sound for the happens-before memory model, which is weaker than most common memory models, including sequential consistency and the Java Memory Model. We implement a null-pointer analysis for concurrent Java programs and show it to be more precise than the traditional analysis.
2016-09-14T00:00:00ZACE-Model: A Conceptual Evolutionary Model For Evolutionary Computation And Artificial LifeDukkipati, Ambedkarhttps://etd.iisc.ac.in/handle/2005/39202021-07-12T05:41:38Z2005-02-07T09:44:59ZACE-Model: A Conceptual Evolutionary Model For Evolutionary Computation And Artificial Life
Dukkipati, Ambedkar
Darwinian Evolutionary system - a system satisfying the abstract conditions: reproduction with heritable variation, in a finite world, giving rise to Natural Selection encompasses a complex and subtle system of interrelated theories, whose substantive transplantation to any artificial medium let it be mathematical model or computational model - will be very far from easy. There are two motives in bringing Darwinian evolution into computational frameworks: one to understand the Darwinian evolution, and the other is to view Darwinian evolution - that carries out controlled adaptive-stochastic search in the space of all possible DNA-sequences for emergence and improvement of the living beings on our planet - as an optimization process, which can be simulated in appropriate frameworks to solve some intractable problems. The first motive led to emerging field of study commonly referred to as Artificial Life, and other gave way to emergence of Evolutionary Computation, which is speculated to be the only practical path to the development of ontogenetic machine intelligence. In this thesis we touch upon all the above aspects.
Natural selection is the central concept of Darwinian evolution and hence capturing natural selection in computational frameworks which maintains the spirit of Darwinian evolution in the sense of conventional, terrestrial and biological perspectives is essential. Naive models of evolution define natural selection as a process which brings in differential reproductive capabilities in organisms of a population, and hence, most of the evolutionary simulations in Artificial Life and Evolutionary Computation implement selection by differential reproduction: the Attest members of the population are reproduced preferentially at the expense of the less fit members of the population. Formal models in evolutionary biology often subdivide selection into components called 'episodes of selection' to capture the different complex mechanisms of nature by which Darwinian evolution can occur. In this thesis we introduce the concept of 'episodes of selection' into computational frameworks of Darwinian evolution by means of A Conceptual Evolutionary model (ACE-model). ACE-model is proposed to be simple and yet it captures the essential features of modern evolutionary perspectives in evolutionary computation framework.
ACE-model is rich enough to offer abstract and structural framework for evolutionary computation and can serve as a basic model for evolutionary algorithms. It captures selection in two episodes in two phases of evolutionary cycle and it offers various parameters by which evolutionary algorithms can control selection mechanisms. In this thesis we propose two evolutionary algorithms namely Malthus evolutionary algorithms and Malthus Spencer evolutionary algorithms based on the ACE-model and we discuss the relevance of parameters offered by ACE-model by simulation studies.
As an application of ACE-model to artificial life we study misconceptions involved in defining fitness in evolutionary biology, and we also discuss the importance of introducing fitness landscape in the theories of Darwinian evolution.
Another important and independent contribution of this thesis is: A Mathematical Abstraction of Evolutionary process. Evolutionary process is characterized by Evolutionary Criteria and Evolutionary Mechanism which are formalized by classical mathematical tools. Even though the model is in its premature stage to develop any theory based on it, we develop convergence criteria of evolutionary process based on this model.
2005-02-07T09:44:59ZAchieving Fairness in the Stochastic Multi-Armed Bandit ProblemPatil, Vishakhahttps://etd.iisc.ac.in/handle/2005/51292021-05-31T10:14:05ZAchieving Fairness in the Stochastic Multi-Armed Bandit Problem
Patil, Vishakha
The classical Stochastic Multi-armed Bandit (MAB) problem provides an abstraction for many
real-world decision making problems such as sponsored-search auctions, crowd-sourcing, wireless
communication, etc. In this work, we study FAIR-MAB, a variant of the MAB problem, where, in
addition to the goal of maximizing the sum of expected rewards, the algorithm also has to ensure
that each arm is pulled for at least a given fraction of the total number of rounds which imposes an
additional fairness constraint on the algorithm. The non-trivial aspect of FAIR-MAB arises when
the time horizon T is unknown to the algorithm. The literature on fairness in the MAB setting
centers around procedural fairness where the fairness guarantee is in terms of the decision-making
process followed by the algorithm rather than in terms of the outcome of the decisions made by
the algorithm. In contrast to this, we consider an outcome-based fairness notion which can be
validated based on the decision of the algorithm.
Our primary contribution is characterizing a class of algorithms for the FAIR-MAB problem by
two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We define
an appropriate notion of fairness and show that our algorithm guarantees fairness independent
of the choice of the learning algorithm. We define the notion of fairness-aware regret which
naturally extends the conventional notion of regret, and show that the fairness-aware regret of
our algorithm matches in order, the regret of the black-box learning algorithm in the absence of
fairness constraints. Finally, we show via detailed simulations that our algorithm outperforms
the best known algorithm for the FAIR-MAB problem in terms of the fairness guarantee that it
provides, while performing comparably in terms of the fairness-aware regret. We also evaluate the
cost of fairness in the MAB setting in terms of the conventional notion of regret