:PROPERTIES:
:ID:       0e70c535-b145-42d9-a9ed-fe48cddbb1a5
:END:
#+title: ISE Week 5
#+filetags: :uni:notes:

* TODO Model free Tuning (for ORM) (pages 9-17)
* TODO Model free Tuning (BestConfig) (pages 18-23)


* 5.1 Model-Free Tuning for ORM Systems - Intelligent Software Engineering

** 1. Introduction and Background

- This approach was proposed by Singh et al. (2016).
- The goal is to optimize Object-Relational Mapping (ORM) systems without relying on models.
- Uses **NSGA-II**, a multi-objective evolutionary algorithm, to handle **multiple performance concerns**.

Reference: Singh, Ravjot et al. *"Optimizing the performance-related configurations of object-relational mapping frameworks using a multi-objective genetic algorithm."* ACM/SPEC ICPE 2016.

** 2. Architecture and Setup

- Focuses exclusively on **binary configuration options**.
- Example of a configuration: `{0011}` – a binary vector where each bit represents a configuration toggle (on/off).
- Evaluates performance using three objective metrics:
  - **Execution time**
  - **CPU load**
  - **Memory consumption**
- Other components follow the standard NSGA-II flow: selection, crossover, mutation, and fitness evaluation.

** 3. Stopping Criteria

Two specific stopping rules are proposed for determining when to terminate the evolutionary process:

*** a. Setting 1: t-test-based Stopping

- Conducts statistical **t-tests** to compare changes in objective values between generations.
- For each pair of consecutive generations \( g_i \) and \( g_j \):
  - Run a t-test on ∆CPU and ∆MEM between all configurations in both generations.
- If **all p-values > 0.05** for **two consecutive generations**, it indicates **no statistically significant improvement**, and the algorithm is stopped.

*** b. Setting 2: Mutual Dominance Rate (MDR)

- Measures how much progress is made by comparing the current and previous generation.
- Let:
  - Set A = configurations from the previous generation
  - Set B = configurations from the current generation
- Define \( dom(A,B) \) as the number of configurations in A that are **dominated** by any configuration in B.

Interpretation:
- **MDR = 0**: No progress — performance plateau
- **MDR < 0**: Regression — performance is deteriorating
- **MDR > 0**: Improvement — current generation is better than the last

** 4. Termination Condition

- The tuning process should stop if **any** of the defined stopping conditions (t-test or MDR) are met.

** 5. Experimental Results

- NSGA-II consistently found configurations that ranked within the **top 25%** of all possible configurations across tested applications.
- Results were obtained by combining different **aggregation functions** and **stopping rules**, demonstrating strong generalization and effectiveness.


* 5.2 Model-Free Tuning with BestConfig - Intelligent Software Engineering

** 1. Introduction and Background

- BestConfig is a model-free configuration tuning system proposed by **Zhu et al. (2017)**.
- It focuses on tuning for **a single performance objective** (e.g., throughput, latency).
- Utilizes **local search techniques** rather than global evolutionary approaches.
- Employs **label encoding** for parameters (e.g., {0, 23, 100}).
- Key strategy: aggressively explore **promising regions** of the configuration space.

Reference: Zhu, Yuqing et al. *"BestConfig: tapping the performance potential of systems via automatic configuration tuning."* SoCC 2017.

** 2. Architecture Overview

- BestConfig is designed to intelligently search a high-dimensional configuration space.
- Architecture relies on two core components:
  - DDS (Divide & Diverge Sampling)
  - RBS (Recursive Bound & Search)

** 3. DDS: Divide & Diverge Sampling

- Purpose: Ensures **coverage** of the entire configuration space by dividing it into **subspaces**.
- Process:
  1. Each configuration parameter's range is divided into **k intervals**.
  2. These intervals are combined across all parameters, forming \( k^n \) subspaces.
  3. **One random sample** is taken from each subspace.

- Advantages:
  - Avoids bias in sampling (common in uniform random search).
  - More likely to sample from all areas of the space.
  - Especially useful in **high-dimensional spaces**.

** 4. RBS: Recursive Bound & Search

- Purpose: Locally refines and improves the best-known configuration.
- Steps:
  1. Identify the best-performing configuration \( C_0 \) from the initial samples.
  2. Define **bounds** for each parameter based on neighboring values around \( C_0 \).
  3. Sample new points within this bounded space to find a better configuration \( C_1 \).
  4. Repeat the bounding and sampling process **recursively** until no improvement is found.

- Bound Definition:
  - For each parameter value in \( C_0 \), the closest lower and higher values in the dataset are chosen as bounds.

- Termination Conditions:
  - If no better configuration is found in a recursive round, the search **restarts from a broader space**.
  - The entire tuning process **stops** only when a **predefined resource budget** (e.g., time, evaluations) is exhausted.

** 5. Results and Observations

- BestConfig consistently finds configurations **significantly better than the system’s default settings**.
- Achieves these improvements within a **reasonable time frame**, making it practical for real-world use.