Cluster-Based Design Space Exploration Framework

A High Level Synthesis (HLS) Design Space Exploration (DSE) framework, developed by me under the supervision of Prof. Laura Pozzi and Dr. Giovanni Ansaloni form Università della Svizzera italiana (USI). The framework enables to smartly navigate the design space aiming at selecting only solutions estimated to be Pareto optimal.

It implements a cluster-based heuristic that, by only exploring a subset of possible configurations for an HLS design, is able to retrieve a close approximation of its Pareto Frontier of non-dominated implementations. The framework identifies regions of interest in the design space, and iteratively searches for new solutions within such regions, or in their combinations.

The proposed framework is independent both from the HLS tools and to the directives chosen for the exploration.

For more details about the Cluster-Based Design Space Exploration methodology you can refer to:

2017 Cluster-Based Heuristic for High Level Synthesis Design Space Exploration
L. Ferretti, G. Ansaloni, and L. Pozzi. Cluster-Based Heuristic for High Level Synthesis Design Space Exploration. IEEE Transactions on Emerging Topics in Computing 2018.

How to run the framework

To run the framework you have to download the functions implementing the Cluster-Based DSE methodology included in the ClusterBasedDSE_MatlabCode.zip file, and a dataset like the ones in the ClusterBasedDSE_Datasets.zip file. Once downloaded, unzip the two archives and run the code inside the ClusterBasedDSE_Datasets folder withouth changing the folder structure.
In order to execute properly the code, your folder stucture should appear similar to the following one:

Datasets

In order to test the Cluster-Based DSE methodology, we have used 5 different benchmarks. We have selected 5 different functions from the CHStone benchmark suite. For each of these functions we have chosen a subset of directives to explore with an HLS tool and we have performed an exhaustive exploration over the defined design space. The datasets have been generated synthesizing the functions with Vivado HLS. Then, we have used the results of the exhaustive exploration and the configurations used to generate the different hardware implementations to test our framework. The functions selected are:

  • ChenIDCt from JPEG benchmark.
  • encode from ADPCM benchmark.
  • decode from ADPCM benchmark.
  • Autocorrelation from GSM benchmark.
  • Reflection_coefficients from GSM benchmark.

The results of the exhaustive explorations are stored in SQLite dataset files named <benchmark_name>.db, and for each of these databases there is a Matlab script named <benchmark_name>.m which prepares the data for the ClusterBasedDSE.m exploration script. The <benchmark_name>.m scripts use the Database Toolbox from Matlab to create a SQLite connection with the databeses. The sqlite function invoked by the script requires the R2016a or later versions of Matlab.

Matlab code

The framework has been entirely developed in Matlab and, in order to use it, requires the Statistics and Machine Learning Toolbox.

To perform an exploration, use the ClusterBasedDSE.m Matlab script.
Before running the script, the following options are needed:

  • benchmarksList: list containing the indices referring to the benchNames entries;
  • nOfExplorations: number of exploration to perform for each benchmark;
  • samplingStrategy: initial sampling strategy;
  • initialSamplingPercentage: size of the initial sample;
  • clustTradeOffList: tradeoff among the number of clusters and how much to prune the design space;
  • visualize_plots: option to generate a visual output;
  • saveData: option to store output data on a file;
For an example on how to run the script and how to set properly the options, have a look at the ClusterBasedDSE.m file available in the package for the download.

The script calls the clusterbased_expl function, which implements the cluster-based methodology, according to the specified options.

The function, starting from an initial set of configurations (sample) previously synthesized by an HLS tool, performs an exploration of the design space specified in input (data). The function requires to specify the admissible configuration values (featureSets and discretizedFeatureSets) for each feature, an option that specifies to normalize the design space or not (normalizeData) and a clustering trade-off factor (clustTradeOff) to tune the exploration process.
During the exploration, the function generates new synthesizable configurations according to the input provided. The function simulates the synthesis process retrieving the area and latency values corresponding to a specific configuration generated during the execution. The area and latency data are included in the data received in input and these values have been generated with an exhaustive exploration of the design space previously performed.

At the end of each exploration the following data are generated:

  • startADRS: initial average distance from reference set (ADRS) among the Pareto frontier of the synthesized solution (sampling set) and the real Pareto frontier;
  • onlineADRS: ADRS evolution during the exploration among the Pareto frontier of the synthesized solution and the real Pareto frontier;
  • startingPP: starting set of Pareto solutions;
  • finalPP: set of Pareto solution at the end of the exploration;
  • synthNum: number of synthesis performed during the exploration;
  • sampledData: set containing all the sampled configurations and the correlated results;

If the saveData option is enabled all these data are saved on file. If visualize_plots option is enabled 3 figures are generated:

  • Boxplot figure: 3 boxplots showing: 1) the final ADRS obtained for all the performed exploration; 2) the initial ADRS before the exploration and 3) the number of synthesis required by the different explorations.

    Fig: Example of Boxplot figure generated after the execution on 100 explorations for ChenIDCt.
  • ADRS evolution figure: average ADRS evolution with respect to the number of synthesis.

    Fig: Example of ADRS evolution figure generated after the execution on 100 explorations for ChenIDCt.
  • Exhaustive exploration vs Cluster-Based DSE: comparison among an exhaustive exploration and an exploration guided by our framework (figure generated only if a single exploration is executed).

    Fig: Example of an exhaustive exploration compared with the cluster-based heuristic. The x are the result of exhaustive exploration, while the dots (dark and light) are the design points explored by our heuristic. Dark dots represent the retrieved Pareto solution.

Author

Lorenzo Ferretti, Ph.D. student at Università della Svizzera italiana (USI).
You can find more information about my work here and for any question you can contact me at lorenzo.ferretti@usi.ch.