Opened 7 months ago

Last modified 7 months ago

#2919 reviewing enhancement

Packed storage matrix type

Reported by: bburlacu Owned by: swagner
Priority: medium Milestone: HeuristicLab 3.3.x Backlog
Component: Data Version: trunk
Keywords: Cc:

Description (last modified by bburlacu)

Dense, fixed-size, symmetric matrices are pretty common. In HeuristicLab they are used for for storing similarities where for example we have code like this:

if (IsCommutative) {
  Parallel.For(0, individuals.Count, parallelOptions, i => {
    for (int j = i; j < individuals.Count; j++) {
      similarityMatrix[i][j] = similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
    }
  });
}

This data could be more compactly stored by using a packed storage scheme (https://en.wikipedia.org/wiki/Packed_storage_matrix) leading to significant savings when storing experiments where each run contains similarity matrices (genotype, phenotype).

Advantages:

  • compact storage
  • more efficient parallelization along the length of the storage array (as opposed to the snipped above where each thread does a different amount of work)

Disadvantages:

  • packed storage prevents vectorization in case of indexed access, which might lead to worse performance (compared to a regular matrix)
  • would require refactoring of the SolutionSimilarityCalculator & friends

Change History (6)

comment:1 Changed 7 months ago by bburlacu

  • Description modified (diff)

comment:2 Changed 7 months ago by bburlacu

  • Status changed from new to accepted

comment:3 Changed 7 months ago by bburlacu

  • Owner changed from bburlacu to gkronber
  • Status changed from accepted to reviewing

r15931: Implement TriangularMatrix deriving from ValueTypeMatrix. This choice was made to support multiple data types without having separate TriangularIntMatrix, TriangularDoubleMatrix, etc. Validation becomes more difficult but it is a compromise for a more generic matrix type.

comment:4 Changed 7 months ago by bburlacu

  • Owner changed from gkronber to bburlacu

comment:5 Changed 7 months ago by bburlacu

  • Owner changed from bburlacu to swagner

r15932: Decide to enforce symmetry by returning values mirrored across the main diagonal.

comment:6 Changed 7 months ago by bburlacu

r15934: Update project (include TriangularMatrix.cs)

Note: See TracTickets for help on using tickets.