Efficient design space exploration for application specific systems-on-a-chip

https://doi.org/10.1016/j.sysarc.2007.01.004Get rights and content

Abstract

A reduction in the time-to-market has led to widespread use of pre-designed parametric architectural solutions known as system-on-a-chip (SoC) platforms. A system designer has to configure the platform in such a way as to optimize it for the execution of a specific application. Very frequently, however, the space of possible configurations that can be mapped onto a SoC platform is huge and the computational effort needed to evaluate a single system configuration can be very costly. In this paper we propose an approach which tackles the problem of design space exploration (DSE) in both of the fronts of the reduction of the number of system configurations to be simulated and the reduction of the time required to evaluate (i.e., simulate) a system configuration. More precisely, we propose the use of Multi-objective Evolutionary Algorithms as optimization technique and Fuzzy Systems for the estimation of the performance indexes to be optimized. The proposed approach is applied on a highly parameterized SoC platform based on a parameterized VLIW processor and a parameterized memory hierarchy for the optimization of performance and power dissipation. The approach is evaluated in terms of both accuracy and efficiency and compared with several established DSE approaches. The results obtained for a set of multimedia applications show an improvement in both accuracy and exploration time.

Introduction

The design flow of a SoC features the combined use of heterogeneous techniques, methodologies and tools with which an architectural template is gradually refined step by step on the basis of functional specifications and system requirements. Each phase in the design flow can be considered as an optimization problem which is resolved by defining and/or setting some of the system’s free parameters in such a way as to optimize certain performance indexes. These optimization problems are usually tackled by means of processes based on successive cyclic refinements: starting from an initial system configuration, they introduce transformations at each iteration in order to enhance its quality. In this paper we focus on Platform-based design. In particular we refer to a design flow based on parameterized SoC platforms. With the term “platform” we intend a coordinated family of hardware–software architectures developed to promote high levels of re-use of hardware and software components in the rapid, low-risk design of application-oriented derivative products. These could take the form of a SoC or more complex electronic systems, and the platforms will be offered by a number of different vendors working in various product application domains, in the form of both relatively fixed platforms and ones incorporating reconfigurability.

The apparent rigidity of a platform, due to a fixed architecture, is made flexible by means of a high degree of programmability and great parameterizations of the modules it contains [1]. Variations in parameters have a considerable impact on the performance indexes being optimized (such as performance, power consumption, area, etc.). Defining strategies to “tune” parameters so as to establish the optimal configuration for a system is a challenge known as Design Space Exploration (DSE). Obviously, it is computationally unfeasible to use an exhaustive exploration strategy. The size of the design space grows as the product of the cardinalities of the variation sets for each parameter. In addition, evaluation of a single configuration almost always requires the use of simulators or analytical models which are often highly complex. Another problem is that the objectives being optimized are often conflicting. The result of the exploration will therefore not be a single solution but a set of tradeoffs which make up the Pareto set.

Any DSE technique can be schematically represented as in Fig. 1. Starting with a base configuration, the exploration process is an iterative refinement process comprising two main stages: evaluation and tuning of the parameters of the configuration. The evaluation phase often boils down to a system-level simulation which constitutes a bottleneck in the exploration process. The tuning phase uses the results of the evaluation phase to modify the system configuration parameters so as to optimize certain performance indexes. The cycle ends when a system configuration that meets the design constraints has been obtained, or, more frequently, when a set of Pareto-optimal configurations for the indexes to be optimized have been accumulated.

The main objective of a design space exploration strategy is to minimize the exploration time while guaranteeing good-quality solutions. Most contribution to DSE to be found in literature address the problem in two complementary ways either by minimizing the number or configurations visited (i.e., simulated), or by minimizing the time required to evaluate (i.e., simulate) the system configurations visited (see Fig. 2). Works [2], [3], [4] belong to the first category. In [2] Givargis et al. propose an exact technique based on the notion of dependence between parameters. The basic idea of their approach is to cluster dependent parameters and then carry out an exhaustive exploration within these clusters. If the size of these clusters increases too much due to great dependency between the parameters, the approach becomes a purely exhaustive search, with a consequent loss of efficiency. To deal with these problems approximate approaches have been proposed in literature which further reduce the exploration space but give no guarantee that the solutions found will be optimal. Fornaciari et al. in [3] use sensitivity analysis to reduce the space of exploration from the product of the cardinalities of the sets of variation of the parameters to their sum. This approach can be seen as a simplified version of [2], as all the parameters are considered to be independent. In this way exploration is carried out by fixing the less sensitive parameters and varying the most sensitive parameter until the objective is optimized. Another approximate approach was proposed by Ascia et al. in [4]. They propose the use of multi-objective genetic algorithms as optimization technique for DSE. Other DSE approaches which perform the pruning of the design space can be found in [5], [6], [7], [8]. Most of the approaches belonging to the second category are of limited applicability and not general (or scalable) since they are often tailored for a specific system architecture. The use of an analytical model to speed up evaluation of a system configuration is presented in [9]. Statistical simulation is used in [10] to enable quick and accurate design decisions in the early stages of computer design, at the processor and system levels. A recent approach [11] uses statistical simulation to speed up the evaluation of configurations by a multi-objective genetic algorithm.

In this paper we propose an approach which tackles the problem on two fronts: the prune of the design space and the reduction of the time required to evaluate system configurations. To achieve this, we propose the use of a Genetic Fuzzy System to increase efficiency or, with the same level of efficiency, improve the accuracy of any DSE strategy. We propose the use of a genetic algorithm as exploration heuristic and a fuzzy system as an evaluation tool. The methodology proposed is applied to the exploration of the design space of a parameterized SoC platform based on a VLIW processor. The use of such platforms for the development of advanced applications, above all in the mobile multimedia area is a representative testbed to evaluate the methodology proposed. The high degree of parametrization that these platforms feature, combined with the heterogeneous nature of the parameters being investigated, both hardware (architectural, micro-architectural and technology-dependent parameters) and software (compilation strategies and application parameters), demonstrates the scalability of the approach.

The rest of the paper is organized as follows. A formal statement of the problem is given in Section 2. Section 3 outlines some of contributions representing the state of the art of DSE techniques proposed in the literature. Section 4 gives a general description of our proposal. Section 5 present the simulation framework and the quality measures we used to assess and compare the performances of the proposed algorithm. In Section 6 the methodology is applied to real case studies and compared, in terms of both efficiency and accuracy, with methodologies presented in Section 3. Finally Section 7 summarizes our contribution and outlines some directions for future work.

Section snippets

Formulation of the problem

Although the methodology we propose is applied to and evaluated on a specific case study (optimization of a highly parameterized VLIW-based SoC platform), it is widely applicable. For this reason, in this section we will provide a general formulation of Design Space Exploration problem.

Let S be a parameterized system with n parameters. The generic parameter pi, i  {1, 2,  , n} can take any value in the set Vi. A configuration c of the system S is a n-tuple 〈v1, v2,  , vn〉 in which vi  Vi is the value

Design space exploration approaches

In this section we will present and discuss three approaches to DSE. The first, GA, uses Genetic Algorithms as the optimization engine. A configuration is mapped onto a chromosome and a population of configurations is made to evolve until it converges on the Pareto-optimal set. The second approach, PBSA (Pareto Based Sensitivity Analysis), uses sensitivity analysis to order the parameters by importance. Each parameter is thus made to vary independently of the others, the immediate consequence

The genetic fuzzy approach for design space exploration

Unfortunately, the approaches introduced in the previous section may be expensive (sometimes computationally infeasible) when a single simulation (i.e., the evaluation of a single system configuration) requires a long compilation and/or execution time. For the sake of example, referring to the computer system architecture considered in this paper, Table 1 reports the computation effort needed for one evaluation (i.e. simulation) of just a single system configuration for several media and

Simulation framework and quality measures

In this section we present the simulation framework we used to evaluate the fitness objectives, and the quality measures we used to assess and to compare the proposed approach.

Comparison between methods

In this section we perform an extensive evaluation of the proposed approach by the comparison with the DSE approaches presented in Section 3. The comparison is carried out in terms of both accuracy and efficiency, on the parameterized system architecture described in Section 5. Efficiency can be defined as the number of system configurations simulated to complete the exploration, and is proportional to the execution time of the exploration algorithm. Accuracy is an index of quality of the

Conclusion and future works

In this paper we presented a new DSE approach based on a Hierarchical Fuzzy System hybridized with a Genetic Algorithm. The approach reduces the number of simulations while minimizing the time required to simulate: GA smartly explores the design space, in the meanwhile the FS learn from the experience accumulated during the GA evolution, storing knowledge in fuzzy rules. The joined rules build the Knowledge Base through which the integrated system quickly predict the results of complex

Giuseppe Ascia received the Laurea degree in electronic engineering and the Ph.D. degree in computer science from the Università di Catania, Italy, in 1994 and 1998, respectively. In 1994, he joined the Institute of Computer Science and Telecommunications at the Università di Catania. Currently, he is an Associate Professor at the Università di Catania. His research interests are soft computing, VLSI design, hardware architectures, and low-power design.

References (34)

  • C.J. Alpert et al.

    Recent developments in netlist partitioning: a survey

    VLSI Journal

    (1995)
  • F. Vahid et al.

    Platform tuning for embedded systems design

    IEEE Computer

    (2001)
  • T. Givargis et al.

    System-level exploration for Pareto-optimal configurations in parameterized System-on-a-Chip

    IEEE Transactions on Very Large Scale Integration Systems

    (2002)
  • W. Fornaciari et al.

    A sensitivity-based design space exploration methodology for embedded systems

    Design Automation for Embedded Systems

    (2002)
  • G. Ascia et al.

    A multi-objective genetic approach for system-level exploration in parameterized systems-on-a-chip

    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

    (2005)
  • G. Hekstra, D.L. Hei, P. Bingley, F. Sijstermans, TriMedia CPU64 design space exploration, in: International Conference...
  • S.G. Abraham, B.R. Rau, R. Schreiber, Fast design space exploration through validity and quality filtering of subsystem...
  • R. Szymanek, F. Catthoor, K. Kuchcinski, Time–energy design space exploration for multi-layer memory architectures, in:...
  • S. Neema, J. Sztipanovits, G. Karsai, Design-space construction and exploration in platform-based design, Tech. Rep....
  • A. Ghosh et al.

    Cache optimization for embedded processor cores: an analytical approach

    ACM Transactions on Design Automation of Electronic Systems

    (2004)
  • L. Eeckhout et al.

    Statistical simulation: adding efficiency to the computer designer’s toolbox

    IEEE Micro

    (2003)
  • S. Eyerman, L. Eechhout, K.D. Bosschere, Efficient design space exploration of high performance embedded out-of-order...
  • P. Mazumder et al.

    Genetic algorithms for VLSI design

    Layout & Test Automation

    (1999)
  • C.J. Alpert, L.W. Hagen, A.B. Kahng, A hybrid multilevel/genetic approach for circuit partitioning, in: Fifth ACM/SIGDA...
  • K. Shahookar et al.

    A genetic approach to standard cell placement using metagenetic parameter optimization

    IEEE Transactions on Computer-Aided Design

    (1990)
  • J. Lienig et al.

    A genetic algorithm for channel routing in VLSI circuits

    Evolutionary Computation

    (1993)
  • Y.-M. Jiang, K.-T. Cheng, A. Krstic, Estimation of maximum power and instantaneous current using a genetic algorithm,...
  • Cited by (82)

    • Automated exploration of datapath and unrolling factor during power-performance tradeoff in architectural synthesis using multi-dimensional PSO algorithm

      2014, Expert Systems with Applications
      Citation Excerpt :

      The main drawback of this approach besides requiring manual intervention to decide the optimal UF, considers only UFs as potential candidates which evenly divided the iteration count. Work presented in Ascia, Catania, Di Nuovo, Palesi, and Patti (2007) for DSE suggests that authors used an evolutionary algorithm for successful evaluation of the design for an application specific SoC. In addition to above, in Mandal et al. (2000), authors have applied GA to the binding and allocation phase.

    • MO-PSE: Adaptive multi-objective particle swarm optimization based design space exploration in architectural synthesis for application specific processor design

      2014, Advances in Engineering Software
      Citation Excerpt :

      Their work employs robust search capacities of the GA to resolve datapath synthesis of scheduling and allocation of resources. The fitness function in above approaches [8–11,4] does not use total execution time (as a function of latency, initiation interval and pipelined data sets) as objective parameter. In [3], the authors used multi structure chromosome representation for the datapath nodes for scheduling.

    View all citing articles on Scopus

    Giuseppe Ascia received the Laurea degree in electronic engineering and the Ph.D. degree in computer science from the Università di Catania, Italy, in 1994 and 1998, respectively. In 1994, he joined the Institute of Computer Science and Telecommunications at the Università di Catania. Currently, he is an Associate Professor at the Università di Catania. His research interests are soft computing, VLSI design, hardware architectures, and low-power design.

    Vincenzo Catania received the Laurea degree in electrical engineering from the Università di Catania, Italy, in 1982. Until 1984, he was responsible for testing microprocessor system at STMicroelectronics, catania, Italy. Since 1985 he has cooperated in research on computer network with the Istituto di Informatica e Telecomunicazioni at the Università di Catania, where he is a Full Professor of computer science. His research interests include performance and reliability assessment in parallel and distributed system, VLSI design, low-power design, and fuzzy logic.

    Alessandro Di Nuovo received the Dr.Eng. degree in computer engineering from the University of Catania, Italy, in 2005. Since 2004 he has cooperated in research with the Department of Computer and Telecommunications at the University of Catania, where he is currently a Ph.D. Student. His main activities regard computational intelligence and its applications in computer, medical and social sciences, parallel and distributed systems, hardware/software co-design.

    Maurizio Palesi received the Laurea degree and the Ph.D. degree in computer engineering from Università di Catania, Italy, in 1999 and 2003, respectively. Since December 2003, he has held a research contract as Assistant Professor at the Dipartimento di Ingegneria Informatica e delle Telecomunicazioni, Facoltà di Ingegneria, Università di Catania. His research focuses on Platform based system design, design space exploration, low-power techniques for embedded systems, and Network-on-Chip architectures.

    Davide Patti received the Laurea degree and the Ph.D. degree in computer engineering at University of Catania, in 2003 and 2007, respectively. His research focuses on Platform based system design, design space exploration, low-power techniques for embedded systems, and Network-on-Chip architectures.

    View full text