Add to a variable multiple in cells variables
Utilizing the cache
The reason your function is so slow is because you are traversing your matrix by rows instead of by columns.  This means that every time you load a value from a new row, you are loading it from a different cache line, which is slow compared to reading nearby values (from the same row and cache line).
I modified your function to take the whole table as input and traverse it in linear fashion, reading all entries in one row before going to the next row.  Your program took 11 seconds, and mine took 1.2 seconds, for an almost 10x speedup.
Here are my changes:
int FindSumOfMinOfColumns(int **tab, int size)
{
    int *minVals = malloc(size * sizeof(*minVals));
    int  row     = 0;
    int  col     = 0;
    int  sum     = 0;

    // Initialize with 0th element of each column.
    memcpy(minVals, tab[0], size * sizeof(*minVals));

    // Compute the minimum of each column.
    for (row = 1; row &lt; size; row++) {
        int *pRow = tab[row];
        for (col = 0; col &lt; size; col++) {
            if (pRow[col] &lt; minVals[col])
                minVals[col] = pRow[col];
        }
    }

    // Sum up the minimum of each column and return it.
    for (col = 0; col &lt; size; col++)
        sum += minVals[col];
    free(minVals);
    return sum;
}

int main(void) {
    // ...

    t1 = RDTSC();
    for (z=0; z&lt;10; z++) // pour avoir une moyenne du temps d'execution
        somme += FindSumOfMinOfColumns(tab, NB);
    t2 = RDTSC();

    // ...
}