Performance Counter Measurements of Data Structures: Implementations for Multi-Objective Optimisation

Abstract

Solving multi-objective optimisation problems using evolutionary computation methods involve the implementation of algorithms and data structures for the storage of tempo- rary solutions. Computational efficiency of these systems becomes important as problems increase in complexity and the number of solutions maintained becomes large. Many data structures and algorithms have been proposed looking to decrease computa- tional times. The effectiveness of a data structure/algorithm can be characterised using wall-clock time. This is a widely used parameter in the literature, however it is strongly dependent on the underlying computer architecture and hence not a reliable measure of absolute performance. A commonly used approach to avoid architectural dependencies is to compare the performance of the data structure being evaluated to the equivalent implementation using a linked list. Modern processors offer built-in hardware performance counters, giving access to a wide set of parameters that can be used to explore performance. In this dissertation we study the efficiency of a non-dominated quad-tree data structure in combination with different evolutionary algorithms using hardware performance counters. We also compare the re- sults for the quad-tree data structure to a linked list as it is the standard practice, however we find non-scalable hardware dependencies might appear.