On the Package

This package contains two main functions to call HRM and MUCH algorithms: HRM_merge(data, anchor_hem, n_pmcs) and MUCH_merge(data, n_pmcs , n_runs, n_sims, dep_lvl). These are the only functions you need to merge the data using one algorithm or the other. On the next sections, we will explain how every part of the algorithm works, which are the internal functions, and how to prepare the inputs necessary to perform the algorithms.

HRM

One way to have common information between subexperiments is to have one HEM in common among all of them. This HEM will serve as link between all the subexperiments, and it is what we call in this package anchor_hem. The choice of the anchor HEM it’s not arbitrary, it should be the HEM that you are most interested in analyzing. That is because, the anchor_hem is the one that will keep the relationship with all other HEMs the most. Once the subexperiments are merged, the values of the anchor_hem w.r.t. the other HEMs will be as if they were measured together. Therefore, one should choose HRM if you want to analyze the behavior of a particular HEM, e.g. PROCESSOR_CYCLES or L2_MISSES, w.r.t. all other HEMs

n_pmcs <- 6
data_hrm <- mergingTools::process_raw_experiments(data = data_hrm_raw_vignette, 
                                                  n_pmcs = n_pmcs)

anchor_hem <- "PROCESSOR_CYCLES"
data_arranged <- data_hrm %>%
  purrr::map(~ .x %>% arrange(!!sym(anchor_hem)))

data_merged <- data_arranged %>%
  purrr::map(~ .x %>% select(-anchor_hem)) %>%
  purrr::reduce(cbind)

DT::datatable(data_merged,
              extensions = 'FixedColumns',
              options = list(scrollX = TRUE,
              scrollCollapse = TRUE))

anchor_data <- purrr::map(data_arranged, ~ .x %>% dplyr::select(anchor_hem)) %>%
  unlist() %>%
  stats::quantile(probs = seq(0, 1, length.out = nrow(data_merged)), type = 2) %>%
  unname()
merged_data <- cbind(anchor_data, data_merged)
names(merged_data)[1] <- anchor_hem

MUCH

HRM has the virtue of being fast to apply because the gathering of the data is very simple. However, one clear flaw is that the relationships between HEMs that were not measured on the same subexperiment are not maintained. HRM works with the anchor_hem primarily and its the HEM that keeps the relationship with all other HEMs. But if one is interested on the relationship of every HEM one needs to put more effort.

MUCH is our proposal for a merge that is closer to the ideal scenario where all HEMs are measured simultaneously. In order to do that, the way we gather the experiments must be different. MUCH requires to have information on every pair of HEMs of the list to analyze. For instance, if we want to analyze 10 HEMs we need to construct the subexperiments so that each HEM is measured at least once with every other HEM. This makes the gathering of data much bigger than on HRM. For instance in the case of 50 HEMs with 6 PMCS, for HRM we need 10 subexperiments, whereas for HRM we need 82 subexperiments. Not only there’s more data to gather, but the way of arranging the subexperiments so that every HEM is paired with every is not trivial. Still, the effort is worth it because the final merge is going to look much closer to the ideal scenario than HRM.

# Data
n_pmcs <- 6
data_much <- mergingTools::process_raw_experiments(data = data_much_raw_vignette, 
                                                  n_pmcs = n_pmcs)
length(data_much)
#> [1] 24

The data is in the same format as HRM, but instead of having only 3 subexperiments now we have 24 because every HEM is measured with every other HEM at least once.

So, why do we need all this data? Our assumption is that we can think of the program at analysis as a function that outputs random variables. Each HEM is a variable of the program, but we can only see a subset of them at once. But, we can construct this unknown function piece by piece. In MUCH we made the assumption to model the mean values of each HEM as a multivariate Gaussian distribution (MVGD). A MVGD needs two inputs, the vector of means and the covariance matrix. The vector of means is straightforward to compute, with the mean value of each HEM separately. The covariance matrix is the object that we must construct piece by piece.

On MUCH, internally we compute the list of all the possible pairs of HEMs that we want to analyze. Then, the first step is going through this list on pair at a time, find a subexperiment where those two HEMs are measured together and compute the correlation between them. If we do this for all HEMs we will have the complete correlation matrix, which contains information about how each HEM behaves with any other HEM.

# Compute the correlation matrix for all HEMs
cor_matrix <- mergingTools::correlation_matrix(splitted_data = data_much)

Now that we have the correlation matrix we can transform it to the covariance matrix and construct the MVGD. But there’s a problem with this matrix, there are HEMs that are highly correlated with one another and have correlation close to 1. This matrix is not invertible, and it cannot be use to construct a MVGD. Therefore, we must get rid of those variables. Do not worry about those variables, they are almost identical to another variable that has been measured and thus do not carry much meaning in the analysis. The variable dep_lvl indicates the degree of dependence allowed on the correlation matrix. For instance, here we put a dep_lvl = 0.85 which means that variables with correlation bigger than 0.85 with another variable are removed. One should aim at tuning this variable as close to one as possible without making the matrix non-invertible.

dep_lvl <- 0.85
# Remove the HEMs which are linearly dependant on other HEMs
cor_matrix_independent <- mergingTools::get_independent_matrix(cor_matrix = cor_matrix, dep_lvl = dep_lvl)

Now we have a suitable correlation matrix and we can generate the MVGD parameters:

# Compute the parameters for the multivariate Gaussian distribution
mvg_params <- mergingTools::generate_mvg_params(splitted_data = data_much, cor_matrix = cor_matrix_independent)

Once we have the covariance matrix and the means vector we can get into the next step. How are we going to use this multivariate Gaussian distribution? We will not use the output of the MVGD as the solution of the merge, because those values are not the real ones. We want to merge the data we gathered from the experiments. So we will use the MVGD as a blueprint to merge them. Suppose that we want to merge the experiments so that the final dataset contains 1000 runs for each HEM. The first step would be to simulate a MVGD of 1000 runs. Now, what this simulation is showing us, is the arrangement that the experimental data needs to have in order to preserve the correlations. You can think of it as the core structure we need to copy into the experimental data. For instance, the sample of the MVGD tells you that in order to preserve all correlations simultaneously, the 5th lowest value of HEM 1 needs to be paired with the 10th lowest value of HEM 2 and the 3rd lowest value of HEM 3, and so on. In the same way that in HRM we arranged the subexperiments based on the order statistics of the anchor_hem, on MUCH we arrange based on the order statistics of the sample of the MVGD. Here is laid out in this image.

The colors represent the order statistics of each HEM, i.e. lighter colors represent lower values while darker colors represent higher values. Once we compute the MVGD sample, we copy the arrangement of the data into the disjointed experimental data. In the last step we have the merged experimental data with the same order structure as the MVGD sample.

In the last step, we will simulate multiple MVGD and arrange the experimental based on them. Then we will keep the arrangement that preserves the correlation matrix the best.

# Simulate several MVGD and merge best on the optimal one
n_sims <- 100
n_runs <- 1000
merged_data <- mergingTools::simulate_and_merge(mvg_params = mvg_params, n_runs = n_runs, n_sims = n_sims, cor_matrix = cor_matrix_independent)

And we have again the final merged dataframe. Using the main function for MUCH, all the code above can be executed with: MUCH_merge(splitted_data = data_much, n_runs = 1000, n_sims = 100, dep_lvl = 0.85)