%% Resource Allocation in DataMill: A Performance Evaluation tool 
%                  Introduction to optimization
%                           ECE 602
%                  Course Project - Winter 2017 
%                     
%          Student Name: Waleed Qadir Khan, Anderson Oliveira
%                     ID. 20359224 , 20647805
%%

%% Problem Formulation
% DataMill is a benchmarking and performance evaluation tool developed at
% the University of Waterloo in collaboration with multiple research
% groups. DataMill is a distributed infrastructure for computer performance
% experimentation on real hardware. The infrastructure varies over a
% selection of hardware and software factors [1]. In this problem, the user must define
% their experiment for Datamill, which in part consists of which package
% the code will run on along with constraints specific to the factors under
% consideration. Through the web interface the user selects all factor levels 
% (e.g. Filesystem type, Compiler optimization level,
% architecture type, etc.)
% that should be activated or deactivated during the execution of an experiment. 
% Each worker machine has its own predefined set of factor levels that they are 
% capable of covering and, for this reason, chances are that moderate to 
% complex experiments can not be executed by only one machine.
% An image of the front-end user interface is given below.
% After the user has submitted their experiment request, the system then selects the
% relevant machines capable of executing the experiments on and herein lies the
% optimization problem. 
% 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].
% Due to the big amount of ongoing experiments and requests, the backend of 
% Datamill has to wisely select the worker machines that cover the
% factors levels specified by the users. Therefore, the solver's job is to minimize the number
% of workers necessary to execute the experiments provided the desired coverage.
% The set of selected workers is represented by a row vector W, and the 
% set of factor levels that will be covered is represented by row vector L

%%
% 
% <<user.png>>
% 

%% Proposed Solution
% The following is the proposed solution outlined in the paper to solve the
% linear program. 
% The objective function followed by the constraints:
%%
% 
% <<formula.png>>
% 
% The variables are defined as follows:[1]% 
%%
% 
% * W is the set of worker machines available in the system. Each position 
% in this vector corresponds to a machine ID. 0 means the machine was not 
% selected and 1 means the machine was selected to execute the experiment.
% * L is the set of factor levels provided by all workers. Each position 
% in this vector corresponds to a level ID. 0 means the level was not 
% selected and 1 means the factor level will be exercised in the experiment.
% * Pm is the set of machines that provide level m. Each column of this 
% matrix represents a level ID, and 0/1 means whether or not the worker is 
% capable to cover this factor level. 
% * Fk is the set of factor levels for factor k (a subset of L). Each 
% column of this matrix represents a level ID, and 0/1 means whether or 
% not the factor has this level id.
% * Bk is the user-requested minimum coverage for factor k. For the relaxed 
% constraint problem, Bk is an scalar containing the sum of all factor 
% levels that should be exercised in the experiment. 
% 

%% Data Sources
% Three pieces of information were required for the program
%%
% 
% # The set of factors from which the user selects the work package: Fk
% # The list of worker machines available and their capabilities w.r.t each
% factor: Pm
% # User provided input submitted to DataMill
% 
% The data files provided in the submission 'fk_datafile.mat' and
% 'pm_datafile.mat' are the hardware collected data for points 1 and 2
% respectively. 

%% Optimization Solution
% The problem is set up as linear, but the one thing to take note of is
% that the values of the workers and factor levels are either 0 or 1 and
% choosing a value in the range of 0 to 1 while might solve the
% optimization problem is not viable since, either a worker is used for the
% work package or it is omitted and same with the factor level. So the
% problem is classified as one having integer constraints. Using the
% default solver provided by CVX (SDPT3) we are solving the relaxed form of
% the integer constraint problem. Below we have solved the problem both
% ways using:
%%
% 
% # SDPT3 - Relaxed constraints
% # GUROBI - Integer constraints
% 
% Gurobi is a professional optimization solver package that can solve
% integer constraint problems. We obtained an academic license to the
% solver and used it as part of our analysis. 

%%% Loading the parameters
clear all; close all;


% Load set of factor level. Fk is a matrix which each row represents each
% factor level
Fk = importdata('fk_datafile.mat');

% Load set of machines that provide level m. Pm is a matrix such that each
% row represents the levels a machine support
Pm = importdata('pm_datafile.mat');

% MACHINES_QUANT number of machines
MACHINES_QUANT = 8;

% FACTORS_QUANTITY: Number of factors
FACTORS_QUANTITY = 14;

% LEVEL_QUANTITY: Total number of factor levels
LEVEL_QUANTITY = 44;

%% Below is an input example of a user-requested minimum coverage for an experiment
frequency_scaling = [1 1]; % Cover frequency saling 'on'  and 'off'
filesystem_type = [0 0 0 0 0 1]; % Cover filesystem BTRFS only
number_of_cores = [0 1 0 0]; % Cover machines with 3 cores
architecture = [0 1]; % Cover x86_64 machines
cpu_clock = [0 0 1 0]; % Select a machine with 2GHz
ram_size = [0 0 0 1 1]; % Select machines with 1 and 2 GB of ram
compiler_type = [1 0]; % Select machines that support GCC
address_randomization = [1 1]; % Cover address randomization ON and OFF
compiler_options = [0 1 0 0]; % Cover complite optimization -O2
memory_padding = [1 0 0 0]; % Cover 0 memory padding
link_order = [0 0 1]; % Cover default link order
cache_dropping = [1 1]; %Cover cache dropping ON and OFF
auto_group = [1 0]; % Cover auto group ON
swap_partition = [1 0]; % Cover swap partition ON

%% Build vector Bk, the user-requested minimum coverage for factors, for the relaxed constraint problem.
Bk = [sum(frequency_scaling);...
    sum(filesystem_type);...
    sum(number_of_cores);...
    sum(architecture);...
    sum(cpu_clock);...
    sum(ram_size);...
    sum(compiler_type);...
    sum(address_randomization);...
    sum(compiler_options);...
    sum(memory_padding);...
    sum(link_order);...
    sum(cache_dropping);...
    sum(auto_group);...
    sum(swap_partition);...
];

%% Solving the optimization problem using SDPT3
cvx_solver sdpt3

cvx_begin
    % W is the set of workers
    variable W(MACHINES_QUANT)
    variable L(LEVEL_QUANTITY)

    minimize sum(W)

    subject to
    
        % ensures picking a factor level means at least one machine with that factor level is added to the solution
        Pm'*W >= L

        % ensures that selecting a machine adds all factor levels it provides to the tally, which is checked
        for j=1:LEVEL_QUANTITY
            for i=1:MACHINES_QUANT
                L(j) >= Pm(i,j)*W(i)
            end
        end

        % Ensures that selecting a machine adds all factor levels it
        % provides to the tally
        Fk*L >= Bk
        
        % Bounds for relaxed constraints. % Relaxed constraints W E [0,1], L E [0,1]
        0 <= W <= 1
        0 <= L <= 1
cvx_end

% store results
selected_machines_relaxed = W;
selected_levels_relaxed = L;

%% Solving the optimization problem using Gurobi
cvx_solver gurobi;

cvx_begin
    % W is the set of workers
    variable W(MACHINES_QUANT) integer
    variable L(LEVEL_QUANTITY) integer

    minimize (sum(W))

    subject to
    
        % ensures picking a factor level means at least one machine with that factor level is added to the solution
        Pm'*W >= L

        % ensures that selecting a machine adds all factor levels it provides to the tally, which is checked
        for j=1:LEVEL_QUANTITY
            for i=1:MACHINES_QUANT
                L(j) >= Pm(i,j)*W(i)
            end
        end

        % guarantees that all user-provided constraints are met
        Fk*L >= Bk
        
        % Relaxed constraints W E {0,1}, L E {0,1}
        0 <= W <= 1
        0 <= L <= 1
cvx_end

%% Comparison between machines selected by gurobi 
% (using integer constraints) vs the default cvx solver (with relaxed constraints)
machines_selected_cvx_gurobi = [selected_machines_relaxed W]

%% Comparison between levels selected by gurobi 
% (using integer constraints) and the default cvx solver (with relaxed constraints)
levels_selected_cvx_gurobi = [selected_levels_relaxed L]

%% Visulizing the data
% Worker set choosen by the Gurobi vs Default Solver
%%
% 
% <<plot.png>>
% 

%% Analysis and Conclusions
% The authors did not provide graphs or data to compare the results
% against, however since the DataMill system is available to use, we
% were able to test out the synthesized data with the actual output. A
% point to note is that for the purpose of the project, not all machines
% available to DataMill were added, and as such the test cases developed
% were such that they were relevant to the selected machine. Our 
% implementation results matched the results generated by the existing
% system. 
% The interesting part regarding the project was to be able to investigate 
% how the optimization problem is solved when the constrains with respect to
% W and L are relaxed, how different solvers can be used to solve this problem
% and what the results provided by the solvers can help us to draw different
% conclusion about their results. The results show that
% while both solvers reach the same optimization value, the optimal point of variables W
% (vector of selected worker machines) and L (vector of factor levels covered)
% are different.
% The plots shown above tells us that Gurobi solved the integer constraint problem
% by choosing two workers for the given set of available workers, while the default
% solver (used for relaxed constraint problem) choose real values in the range of 0 to 1. If
% the authors of the paper used the relaxed constraint version to solve the problem,
% an additional decision  strategy (or heuristics) had to be created in order 
% to select the machines amongst 
% the ones selected by the solver. For example, one could decide to select all 
% machines that had its value greater than 0.1. However, if we do not relax the
% constraints and use gurobi to solve the problem, no additional decision has
% to be made.

%% Further Development
% During our analysis of the results from our code, we discovered that the
% factor levels chosen by the solver deviated at times from those prescribed
% by the user. Further investigating the problem we rooted out the problem
% to how the problem set up the Bk vector. It combines the user inputs per
% factor into a scalar and then processes the data. We experience a loss of
% information in such a structure. We contacted the author of the paper
% and inquired into the behavior and found out this was a design decision
% since DataMill does not guarantee 100% level coverage w.r.t to the user
% input. For the purposes of the project, we decided to improve upon the
% proposed solution in the paper and extend the functionality so that it
% does provide 100% line coverage. The following is the proposed updated
% optimization problem. The entire implementation is provided separately
% in a file called 'extended_solution.m', but the major changes are shown
% below

% Build Bk matrix containing the user requested minimum coverage
% Bk = [frequency_scaling zeros(1,42); ...
% zeros(1,2) filesystem_type zeros(1,36); ...
% zeros(1,8) number_of_cores zeros(1,32);...
% zeros(1,12) architecture zeros(1,30);...
% zeros(1,14) cpu_clock zeros(1,26);...
% zeros(1,18) ram_size zeros(1,21);...
% zeros(1,23) compiler_type zeros(1,19);...
% zeros(1,25) address_randomization zeros(1,17);...
% zeros(1,27) compiler_options zeros(1,13);...
% zeros(1,31) memory_padding zeros(1,9);...
% zeros(1,35) link_order zeros(1,6);...
% zeros(1,38) cache_dropping zeros(1,4);...
% zeros(1,40) auto_group zeros(1,2);...
% zeros(1,42) swap_partition];

% cvx_solver gurobi;
% 
% cvx_begin
%     
%     variable W(MACHINES_QUANT) integer
%     variable L(LEVEL_QUANTITY) integer
% 
%     minimize (ones(1,MACHINES_QUANT)*W)
% 
%     subject to
%     
%        
%         Pm'*W >= L
% 
%         
%         for j=1:LEVEL_QUANTITY
%             for i=1:MACHINES_QUANT
%                 L(j) >= Pm(i,j)*W(i)
%             end
%         end
% 
%         for f=1:FACTORS_QUANTITY
%             L'.*Fk(f, :) >= Bk(f, :);
%         end
%         
%         0 <= W <= 1
%         0 <= L <= 1
% cvx_end
%
%% Results
% The results of the updated solver corresponded to the same minimization
% value as the one described before, with the added benefit of achieving
% 100% level coverage. By using a matrix for the Bk we avoid loss of
% information to the system and hence can generate more precise constraints
% that produce the desired results.


%% Linked files
% Following are all the necessary files associated with the project:
%%
% 
% * problem.m: This is the actual optimization problem stated on the paper
% * extended_solution.m: Our improvements on the optimization solver to achieve 100%
% line coverage
% * fk_datafile.mat: Static data on factor levels from DataMill
% * pm_datafile.mat: Static data on workers from DataMill
% 


%% References
%%
% 
% # Sebastian Fischmeister, Augusto Born de Oliveira, Jean-Christophe,
% Thomas Reidemeister DataMill: Rigorous Performance Evaluation Made Easy, 
% https://pdfs.semanticscholar.org/3f6e/b56461bb589604a0aeefc355ce7ea3345280.pdf% 
