%% Resource Allocation in DataMill: A Performance Evaluation tool
%                Introduction to optimization (ECE 602)
%
%          Students Name: Reza Mirosanlou, Homa Aghilinasab
%
%% Problem Definition
%
% Our assigned paper introduces DataMill which is a community-based open benchmarking. It evaluates 
% the computer performance experiments on real hardware and produces reliable, and 
% reproducible results. The infrastructure varies over a selection of hardware and software factors some of which 
% are hidden. These factors vary for different hardware and software [1]. Multiple research groups Besides 
% the University of Waterloo already participate in DataMill. The design of this infrastructure ask the 
% users to define their experiment factors for Datamill. Then it uses these factors along with constraints 
% specific to the factors to run the code. Some of the factors that the user can define are architecture, 
% compiler optimization level, file system type, etc. The DataMill infrastructure is composed of a master node, 
% responsible for the distribution of experiment trials and the collection of results, and several worker 
% nodes, which execute the experiment packages provided by the users[1]. The problem is then to select the
% minimum number of workers necessary to give the desired factor coverage [1].
%
%% Two test cases
%
% We run the optimization problem for two sets of user data and get the
% results.
%
% <<Interface1.PNG>>
%
% First set factors is as above Figure is shown below:
% 
% * Frequency scaling sets 'ON' and 'OFF';[1 1].
% * File system type should be BTRFS only; [0 0 0 0 0 1].
% * We choose the machine with 3 number of cores; [0 1 0 0].
% * X86_64 is chosen for the machin architecture; [0 1].
% * Clock frequencyu of the CPU is 2GHz; [0 0 1 0].
% * Ram has 1 and 2 GB capacity; [0 0 0 1 1].
% * As a above picture we choose GCC compiler; [1 0].
% * Address randomization 'ON' and 'OFF'; [1 1].
% * Compiler optimization option is chosen O2; [0 1 0 0];
% * Cover zero memory padding; [1 0 0 0].
% * The link order chosen as default; [0 0 1].
% * Cover cache dropping 'ON' and 'OFF'; [1 1].
%  *The auto group parameter chosen as 'ON'; [1 0];
% * The swap partition parameter is 'ON'; [1 0].
% 
% Second set is selected as below Figure and shown below:
% 
% * Frequency scaling sets 'OFF';[1 0].
% * File system type should be BTRFS only; [0 0 0 0 0 1].
% * We choose the machine with 2 number of cores; [0 0 1 0].
% * X86_64 is chosen for the machin architecture; [0 1].
% * Clock frequencyu of the CPU is 4GHz; [0 1 0 0].
% * Ram has 2 GB capacity; [0 0 0 1 0].
% * As a above picture we choose LLVM compiler; [0 1].
% * Address randomization 'OFF'; [1 0].
% * Compiler optimization option is chosen O3; [1 0 0 0];
% * Cover zero memory padding; [1 0 0 0].
% * The link order chosen as Alphabetical; [1 0 0].
% * Cover cache dropping 'OFF'; [1 0].
%  *The auto group parameter chosen as 'OFF'; [1 0];
% * The swap partition parameter is 'ON'; [1 0].
%
% <<Interface2.PNG>>
%
%
%% Proposed Optimization Solution
%
% <<solution.png>>
% 
%
%% Parameter Definition
%
% The variables are defined as follows:[1]
%
% * W is the set of workers.
% * L is the set of factor levels. 
% * $P_m$ is the set of machines that provide level m.
% * $F_k$ is the set of factor levels for factor k (a subset of L).
% * $B_k$ is the user-requested minimum coverage for factor k. 
%
% The value of each element is defined as follows:
%
% * W vector is a set of machine IDs in which zero and one means that either the machine was not selected or not. 
% * L vector structure is the same as W except it is for level IDs.
% * $P_m$ is a matrix which each of its columns represents a level ID, and 0/1 means whether or not the worker is capable of covering this factor level.
% * $F_k$ structure is the same as P_m except each column shows the level id capability.
% * $B_k$ is a vector that each element is the sum of all factor levels.
%
% The reason for each equation is [1]:
%
% * Equation (1b) ensures picking a factor level means at least one machine with that factor level is added to the solution
% * Equation (1c) ensures that selecting a machine adds all factor levels it provides to the tally, which is checked in Equation (1d) for every factor.
% * The last equation guarantees that all user-provided constraints are met.
%
% After a solution is found, each worker is individually selected by their respective $x_i$ variable [1].
%
% The reason of each equation is [1]:
%
% * Equation (1b) ensures picking a factor level means at least onemachine with that factor level is added to the solution
% * Equation (1c) ensures that selecting a machineadds all factor levels it provides to the tally, which is checkedin Equation (1d) for every factor.
% * The last equation guar-antees that all user-provided constraints are met.
%
% After asolution is found, each worker is individually selected bytheir respective $x_i$ variable [1].
%
%% Definition of Factors
%
% The factors which are the part of $B_k$ definition which is involved in the minimization problem are as follows:
% 
% * *Frequency Scaling*: this parameter has two options 'ON' and 'OFF'. By using this factor, we can reduce the frequency of the processor during the execution to save power, but it causes performance loss. Evaluating both levels of this factor is likely to reveal a performance effect.
% * *Type of system file*: Datamill only covers BTRFS file system type. So the content for this parameter is always [0 0 0 0 0 1].
% * *Architecture*:  It shows the architecture of the system. It covers X86_64.
% * *Number of cores*: It defines the number of Cores.
% * *CPU clock*: Show the clock speed of the CPU cores.
% * *RAM size*: The Ram size of the system.
% * *Type of compiler*: It defines the types of the compiler that the user chooses.
% * *Address randomization*: It covers address randomization to be 'ON' and 'OFF'.
% * *Compiler options*: This is the compile optimization that the user chooses. 
% * *Memory padding*: Defines the number of memory padding.
% * *Link order*: Cover the definition of link order.
% * *Cache dropping*: Defines that the dropping cache to be 'ON' or 'OFF'.
% * *Auto group*: It Covers 'ON' and 'OFF' options of an auto group.
% * *Swap partition*: Defines that the switch partition to be 'ON or 'OFF'.
%

%% Optimization Code for the first data set
%
clear all;
close all;

Freq_Scal = [1 1]; %Frequency Saling 
File_Sys_Type = [0 0 0 0 0 1]; % Filesystem BTRFS
N_Cores = [0 1 0 0]; % #Cores
Arch = [0 1]; % Architecture
CLK = [0 0 1 0]; % CPU Clock Frequency
RAM = [0 0 0 1 1]; % RAM Size
Comp = [1 0]; % Compiler Type
Addr_Rand = [1 1]; % Address Randomization
Comp_Opt = [0 1 0 0]; % Compliler Optimization
Mem_Padding = [1 0 0 0]; % Memory Padding
LNK_Ord = [0 0 1]; % Link Order
Cache_Drop = [1 1]; %Cache Dropping
Auto_Gr = [1 0]; % Auto Group
SWAP = [1 0]; % Swap Partition ONs

Bk = [sum(Freq_Scal);
    sum(File_Sys_Type);
    sum(N_Cores);
    sum(Arch);
    sum(CLK);
    sum(RAM);
    sum(Comp);
    sum(Addr_Rand);
    sum(Comp_Opt);
    sum(Mem_Padding);
    sum(LNK_Ord);
    sum(Cache_Drop);
    sum(Auto_Gr);
    sum(SWAP);
];
%in This Example Bk is
%[1,1,1,1,2,1,2,1,1,1,2,1,1]'

P_j = importdata('P_j.txt');
F_k = importdata('F_k.txt');

cvx_begin
	variable W(20);
    variable L(50);
    Wc=sum(W);
    
    minimize Wc
    subject to
    P_j'*W >= L
    for j=1:50
        for i=1:20
            L(j) >= P_j(i,j)*W(i)
        end
    end
	F_k*L >= Bk
	0 <= W <= 1
	0 <= L <= 1
cvx_end

W'
L'

%% Optimization Code for second data set
%
clear all;
close all;

Freq_Scal = [1 0]; %Frequency Saling 
File_Sys_Type = [0 0 0 0 0 1]; % Filesystem BTRFS
N_Cores = [0 0 1 0]; % #Cores
Arch = [0 1]; % Architecture
CLK = [0 1 0 0]; % CPU Clock Frequency
RAM = [0 0 0 1 0]; % RAM Size
Comp = [0 1]; % Compiler Type
Addr_Rand = [1 0]; % Address Randomization
Comp_Opt = [1 0 0 0]; % Compliler Optimization
Mem_Padding = [1 0 0 0]; % Memory Padding
LNK_Ord = [1 0 0]; % Link Order
Cache_Drop = [1 0]; %Cache Dropping
Auto_Gr = [1 0]; % Auto Group
SWAP = [1 0]; % Swap Partition ONs

Bk = [sum(Freq_Scal);
    sum(File_Sys_Type);
    sum(N_Cores);
    sum(Arch);
    sum(CLK);
    sum(RAM);
    sum(Comp);
    sum(Addr_Rand);
    sum(Comp_Opt);
    sum(Mem_Padding);
    sum(LNK_Ord);
    sum(Cache_Drop);
    sum(Auto_Gr);
    sum(SWAP);
];
%in This Example Bk is
%[1,1,1,1,1,1,1,1,1,1,1,1,1]'

P_j = importdata('P_j.txt');
F_k = importdata('F_k.txt');

cvx_begin
	variable W(20);
    variable L(50);
    Wc=sum(W);
    
    minimize Wc
    subject to
    P_j'*W >= L
    for j=1:50
        for i=1:20
            L(j) >= P_j(i,j)*W(i)
        end
    end
	F_k*L >= Bk
	0 <= W <= 1
	0 <= L <= 1
cvx_end

W'
L'
%
%% Results
% In this section we compare the results for our two sets of factors. In
% the first data set as we can see the optimal value is 2, and the sum of
% all the factors is greater than the values of the second factors. Due
% to this fact the results of the L for set 2 are greater than or equal to set1 but for W 
% set2 results are less than or equal to the result of the first set.
%
% <<Graph1.png>>
%
% <<Graph2.png>>
%
%
%
%% Analysis and Conclusions
%
% In this paper the authors did not provide any graphs or data related to their optimization problem to compare our results with them. Although Datamill does not available
% any longer to test them but fortunately, our implementation results matched the results generated by the related works of this paper. The exciting part of the project
% is that if we select the variables W and L as an integer the results
% would be different since the W and L only can be 0 and 1. All in all,
% since the authors have not mentioned about it, we assumed that the values are real numbers between 0 and 1.
%
%% Linked files
% Following are all the necessary files associated with the project:
% 
% * Project.m: The main file
% * F_k.txt: Factor levels test
% * P_j.txt: Workers test
% 
%% References
% 
% # Sebastian Fischmeister, Augusto Born de Oliveira, Jean-Christophe,
% Thomas Reidemeister DataMill: Rigorous Performance Evaluation Made Easy, 
% https://pdfs.semanticscholar.org/3f6e/b56461bb589604a0aeefc355ce7ea3345280.pdf% 
