% ------------- Fault Tolerant Logic Mapping for Nano-Crossbars -----------
%
% This algorithm uses heuristic backtracking for finding a valid mapping. It
% exercise sorting and matching with Hadamard Multiplication
% for a given crossbar.
%
%     Fault Rate (p_o)               :   Decimal e. g. 20% is 0.20
%     Sz                                         :  Sample size
%     sh                                         :  Sheet number of   Benchmark Function
%
%
%     Function Matrix                              Crossbar Matrix
%
%     f = x1 x2 + x2 x3 + x1 x4
%
%     x1  x2  x3  x4                       0: functional  -1:Stuck-open +1: Stuck-closed
%     p1     1    1   0     0                                  0  0  -1  0
%     p2     0   1    1     0                                  0  0  0  1
%     p3     1   0    0     1                                  0  1  0  0


clc
clear
format short
format compact

matrix_file = 'function_matrix.xlsx';

benchmark = 1;     %_________ Benchmark Functions 1 to 11 in Excel File _________
p_o = 0.15;
sz = 50;
permutation = 3000;

% _________ Function File ________

FunctionMatrix =  xlsread(matrix_file, benchmark);
[row , column] = size(FunctionMatrix);

if row < column
    FunctionMatrix = FunctionMatrix';
    [row , column] = size(FunctionMatrix);
end

IR = sum(sum(FunctionMatrix == 1)) / (row*column) ;
FunctionMatrix(FunctionMatrix == 0) = -1;

% __________________________________

ValidMapping = 0;
NoMapping = 0;


ColumnPermutation = zeros(1,sz);
timeVector =zeros(1,sz);
fprintf('FAULT TOLERANT LOGIC MAPPING\n Sample Size = %d\n\n',sz)

for k=1:sz
    fprintf(' k = %d\n', k)
    mapping = false;
    
    cd('CrossbarMatrices');
    fname = sprintf('CM_%dx%d_0.15_%d.mat',row, column, k);
    load(fname);
    cd('..')
    [row_n,column_m] = size(CM);
    
    CrossbarMatrix = CM;
    
    Csub = sort_right(CrossbarMatrix, CrossbarMatrix);
    Csub = Csub(:,1:column);
    Csub = sort_left(Csub, CrossbarMatrix);
    
    Fsub = sort_left(FunctionMatrix, CrossbarMatrix);
    
    [n_f, m_f] = size(Fsub);
    [n_c, m_c] = size(Csub);
    tic
    for per = 1:permutation
        RowMatch = zeros(1, n_f);
        
        if per > 1
            per_column = randperm(m_f);
            Fsub = Fsub(:, per_column);
        end
        
        for k1 = 1:n_f
            
            FsubRow = Fsub(k1,:);
            
            for k2 = 1:n_c
                
                if k2 ~= RowMatch
                    
                    comp = FsubRow.*Csub(k2,:);
                    
                    if all(comp >=0)
                        RowMatch(1, k1) = k2;
                        break
                    end
                end
            end
            
            if RowMatch(1, k1) == 0
                traverse = RowMatch;
                traverse = traverse(traverse >0);
                traverse = fliplr(traverse);
                for k3 = traverse
                    comp = FsubRow.*Csub(k3,:);
                    if all(comp >=0)
                        broken = find(RowMatch == k3);
                        RowMatch(1, broken) = 0;
                        RowMatch(1,k1) = k3;
                        break
                    end
                end
                
                if RowMatch(1,k1) > 0
                    
                    for k4 = 1:n_c
                        FsubRow = Fsub(broken, :);
                        
                        if k4 ~= RowMatch
                            comp = FsubRow.*Csub(k4,:);
                            
                            if all(comp >=0)
                                RowMatch(1, broken) = k4;
                                break
                            end
                            
                        end
                        
                    end
                    
                    if RowMatch(1,broken) == 0
                        RowMatch(1,k1) = 0;
                    end
                    
                end
                
            end
            
            if RowMatch(1,k1) == 0
                break
            end
            
        end
        
        if all(RowMatch > 0)
            mapping = true;
            break
        end
        
        
    end                                % _____ permutation = 3000 end __________
    T = toc;
    fprintf(' Runtime %0.4f\n', T)
    timeVector(1,k) = T;
    if mapping
        display('Valid Mapping')
        ColumnPermutation(1,k) = per-1;
        ValidMapping = ValidMapping +1;
    else
        display('No Mapping')
        ColumnPermutation(1,k) = per-1;
        NoMapping = NoMapping + 1;
    end
    
end

display('_________________________________________________________')


fprintf('Logic Inclusion Ratio = %f\n\n', IR)
c_size =row *column;
fprintf('Function Size (%d x %d) = %d\n\n', row, column, c_size)
fprintf('Crossbar Size (%d x %d) = %d\n\n', row_n, column_m, c_size)
fprintf('Number of Valid Mappings = %d\n', ValidMapping)
fprintf('\n')
fprintf('Number of Failed Mappings = %d\n', NoMapping);
fprintf('\n')
mean_1 = ValidMapping*100 /sz;
mean_1=floor(mean_1);
fprintf('Percentage of Valid Mappings = %d\n', mean_1);
fprintf('\n')
single_time = (sum(timeVector) / sz);
fprintf('Time for each Sample = %f\n\n', single_time)
display(ColumnPermutation)

