DesignSpace.scala 10.7 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
// Copyright (C) 2014 Jens Korinth, TU Darmstadt
//
// This file is part of Tapasco (TPC).
//
// Tapasco is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Tapasco is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with Tapasco.  If not, see <http://www.gnu.org/licenses/>.
//
/**
 * @file     DesignSpace.scala
 * @brief    The DesignSpace class models the discrete design space for TPC hardware
 *           designs. Essentially, it provides a list of configurations consisting of
 *           a composition and target frequency, which can then be passed to the
 *           Compose task to generate a bitstream. Compose can automatically iterate
 *           over the design space in case of failure, thus performing a simple design
 *           space exploration (DSE). DesignSpace offers helper methods to define and
 *           span the design space one is interested in. At the moment there are three
 *           basic dimensions: Frequency, Utilization (i.e., number of instances) and
 *           Alternatives. Variation of the frequency is straightforward; variation of
 *           the utilization modifies the number of instances proportionally (keeping
 *           at least one instance of each core) to optimize the area utilization.
 *           Alternatives considers all kernels with the same ID as alternative
 *           implementations of the same computation and generates all compositions
 *           with all available alternatives. Finally, a heuristic is applied to order
 *           the design space; the heuristic function should encode the optimization
 *           goal in a ordering.
 * @authors  J. Korinth, TU Darmstadt (jk@esa.cs.tu-darmstadt.de)
 **/
package de.tu_darmstadt.cs.esa.tapasco.dse
40
41
42
43
44
45
46
import de.tu_darmstadt.cs.esa.tapasco.base._
import de.tu_darmstadt.cs.esa.tapasco.filemgmt.FileAssetManager
import de.tu_darmstadt.cs.esa.tapasco.util.LogFormatter._
import java.nio.file.Paths

import Heuristics._
import de.tu_darmstadt.cs.esa.tapasco.util.SlotOccupation
47
48
49
50
51
52
53
54
55

class DesignSpace(
    bd: Composition,
    target: Target,
    val heuristic: Heuristic,
    val dim: DesignSpace.Dimensions = DesignSpace.defaultDim,
    val designFrequency: Heuristics.Frequency
  )(implicit cfg: Configuration) {
  import scala.util.Properties.{lineSeparator => NL}
Jens Korinth's avatar
Jens Korinth committed
56
  private[this] final val DEFAULT_CLOCK_PERIOD_NS = 4           // default: 250 MHz
57
58
59
60
61
62
63
64
65
  private[this] val logger = de.tu_darmstadt.cs.esa.tapasco.Logging.logger(this.getClass)
  logger.trace(Seq("DesignSpace(", dim, ")") mkString)

  lazy val feasibleFreqs: Seq[Double] = feasibleFreqs(bd)

  private def feasibleFreqs(bd: Composition): Seq[Double] = if (dim.frequency) {
    val cores = bd.composition flatMap (ce => FileAssetManager.entities.core(ce.kernel, target))
    val srs   = cores flatMap { c: Core => FileAssetManager.reports.synthReport(c.name, target) }
    val cps   = srs flatMap (_.timing) map (_.clockPeriod)
Jens Korinth's avatar
Jens Korinth committed
66
    val fmax  = 1000.0 / (if (cps.nonEmpty) cps.max else DEFAULT_CLOCK_PERIOD_NS)
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
    target.pd.supportedFrequencies map (_.toDouble) filter (_ <= fmax) sortWith (_>_)
  } else {
    Seq(designFrequency)
  }

  lazy val feasibleCompositions: Seq[Composition] = compositions(bd)

  /**
   * Computes the set of feasible compositions for a given base composition.
   * The given composition defines the ratios of the kernels, each kernel will be
   * instantiated at least once.
   **/
  private def feasibleCompositions(bd: Composition): Seq[Composition] = if (dim.utilization) {
    val counts        = bd.composition map (_.count)
    val minCounts     = counts map (n => Seq(java.lang.Math.round(n / counts.min.toDouble).toInt, 1).max)
    val cores         = bd.composition flatMap (ce => FileAssetManager.entities.core(ce.kernel, target))
    val srs           = cores flatMap { c: Core => FileAssetManager.reports.synthReport(c.name, target) }
    val areaEstimates = srs flatMap (_.area)
85
    val slotOccupations = srs map (r => SlotOccupation(r.slaves.get, target.pd.slotCount))
86
87
88
    val targetUtil    = target.pd.targetUtilization.toDouble
    logger.trace("target util = " + targetUtil)

89
    def slotUtil(counts : Seq[Int]) : SlotOccupation = (slotOccupations zip counts).map(o => o._1 * o._2).reduce(_ + _)
90
    // check if there is any feasible composition
91
    if (!slotUtil(minCounts).isFeasible) {
92
93
94
95
      throw new Exception("Composition infeasible! Exceeds maximal slot count of " + target.pd.slotCount
          + " for " + target + "." + NL + bd)
    }

96
    def areaUtil(counts: Seq[Int]) = (areaEstimates zip counts) map (a => a._1 * a._2) reduce(_ + _)
97
    // compute number of steps
98
    val currUtil = areaUtil(minCounts).utilization
99
    val df: Int = Seq(java.lang.Math.round((targetUtil - currUtil) / currUtil).toInt, 1).max
100
101
102
103
    val currSlots = slotUtil(minCounts).slots
    val targetSlots = target.pd.slotCount
    val sf : Int = Math.max(Math.round(targetSlots.toDouble/currSlots.toDouble), 1).toInt
    val steps = Math.min(sf, df)
104
105
106
107

    logger.trace("minCounts = " + minCounts + " currUtil = " + currUtil)

    // compute feasible sequences as multiples of minCounts
108
109
    val seqs = (for (i <- steps to 1 by -1)
      yield minCounts map (n => i * n)) filter (c => areaUtil(c).isFeasible && slotUtil(c).isFeasible)
110
111

    logger.trace("number of feasible counts: " + seqs.length)
112
    if (seqs.isEmpty) {
113
114
115
116
117
      logger.warn("No feasible composition found; please check starting composition ratios: " + NL + bd)
    }

    // make sequence of CompositionEntries
    val ces = for {
118
        s <- seqs filter (_.sum <= target.pd.slotCount)
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
      } yield bd.composition.map(_.kernel) zip s map (x => Composition.Entry(x._1, x._2))

    // make full composition
    ces map (Composition(Paths.get("N/A"), Some("Generated composition."), _))
  } else {
    Seq(bd)
  }

  private def feasibleAlternatives(bd: Composition): Seq[Composition] =
    if (dim.alternatives) Alternatives.alternatives(bd, target) else Seq(bd)

  private def compositions(bd: Composition): Seq[Composition] =
    feasibleAlternatives(bd) map (feasibleCompositions(_)) reduce (_++_)

  lazy val enumerate: Seq[DesignSpace.Element] = (for {
134
      bd <- compositions(bd)
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
      f  <- feasibleFreqs(bd)
    } yield DesignSpace.Element(bd, f, heuristic(bd, f, target)(cfg))) sortBy (_.h) reverse

  // TODO remove this and move to proper dumping helper class
  def dumpC(bd: Composition, sep: String = "; "): String = bd.composition.map(ce => Seq(ce.kernel, " x ", ce.count).mkString).mkString(sep)
  def dump(sep: String = ",", header: Boolean = true): String =
      (if (header) Seq("Composition", "Frequency", "H").mkString(sep) + NL else "") +
      (enumerate map (p => Seq(dumpC(p.composition), p.frequency, p.h) mkString sep)).mkString(NL)
}

object DesignSpace {
  private final val logger = de.tu_darmstadt.cs.esa.tapasco.Logging.logger(getClass)
  private final val NL = scala.util.Properties.lineSeparator

  final case class Dimensions(
      frequency: Boolean    = false,
      utilization: Boolean  = false,
      alternatives: Boolean = false) {
    override lazy val toString: String = "(%s)".format(
      Seq(("freq", frequency), ("area", utilization), ("alternatives", alternatives))
        .filter (_._2) map (_._1) mkString ", ")
  }

  final case class Element(
      composition: Composition,
      frequency: Heuristics.Frequency,
      h: Heuristics.Value
    ) {
    override lazy val toString: String = "Element[Composition: %s, Freq: %3.2f, H: %3.2f]"
      .format(logformat(composition), frequency, h)
  }

  val defaultDim = Dimensions(true, false, false)

  def feasibleFreqs(target: Target, bd: Composition): Seq[Double] = {
    val cores = bd.composition flatMap (ce => FileAssetManager.entities.core(ce.kernel, target))
    val srs   = cores flatMap { c: Core => FileAssetManager.reports.synthReport(c.name, target) }
    val cps   = srs flatMap (_.timing) map (_.clockPeriod)
173
    val fmax  = if (cps.nonEmpty) 1000.0 / cps.max else Double.PositiveInfinity
174
175
176
177
178
179
180
181
182
    target.pd.supportedFrequencies map (_.toDouble) filter (_ <= fmax) sortWith (_>_)
  }

  def feasibleCompositions(target: Target, bd: Composition): Seq[Composition] = if (bd.nonEmpty) {
    val counts        = bd.composition map (_.count)
    val minCounts     = counts map (n => Seq(java.lang.Math.round(n / counts.min.toDouble).toInt, 1).max)
    val cores         = bd.composition flatMap (ce => FileAssetManager.entities.core(ce.kernel, target))
    val srs           = cores flatMap { c: Core => FileAssetManager.reports.synthReport(c.name, target) }
    val areaEstimates = srs flatMap (_.area)
183
    val slotOccupations = srs map (r => SlotOccupation(r.slaves.get, target.pd.slotCount))
184
185
186
    val targetUtil    = target.pd.targetUtilization.toDouble
    logger.trace("target util = " + targetUtil)

187
    def slotUtil(counts : Seq[Int]) : SlotOccupation = (slotOccupations zip counts).map(o => o._1 * o._2).reduce(_ + _)
188
    // check if there is any feasible composition
189
    if (!slotUtil(minCounts).isFeasible) {
190
      throw new Exception("Composition infeasible! Exceeds maximal slot count of " + target.pd.slotCount
191
        + " for " + target + "." + NL + bd)
192
193
    }

194
    def areaUtil(counts: Seq[Int]) = (areaEstimates zip counts) map (a => a._1 * a._2) reduce(_ + _)
195
    // compute number of steps
196
    val currUtil = areaUtil(minCounts).utilization
197
    val df: Int = Seq(java.lang.Math.round((targetUtil - currUtil) / currUtil).toInt, 1).max
198
199
200
201
    val currSlots = slotUtil(minCounts).slots
    val targetSlots = target.pd.slotCount
    val sf : Int = Math.max(Math.round(targetSlots.toDouble/currSlots.toDouble), 1).toInt
    val steps = Math.min(sf, df)
202
203
204
205

    logger.trace("minCounts = " + minCounts + " currUtil = " + currUtil)

    // compute feasible sequences as multiples of minCounts
206
207
    val seqs = (for (i <- steps to 1 by -1)
      yield minCounts map (n => i * n)) filter (c => areaUtil(c).isFeasible && slotUtil(c).isFeasible)
208
209

    logger.trace("number of feasible counts: " + seqs.length)
210
    if (seqs.isEmpty) {
211
212
213
214
215
      logger.warn("No feasible composition found; please check starting composition ratios: " + NL + bd)
    }

    // make sequence of CompositionEntries
    val ces = for {
216
217
      s <- seqs filter (_.sum <= target.pd.slotCount)
    } yield bd.composition.map(_.kernel) zip s map (x => Composition.Entry(x._1, x._2))
218
219
220
221

    // make full composition
    ces map (Composition(Paths.get("N/A"), Some("Generated composition."), _))
  } else {
222
    Seq.empty
223
224
  }
}