System level design space exploration for MPSoC : methods, algorithms and new infrastructure

INSTITUTO UNIVERSITARIO DE SISTEMAS INTELIGENTES Y APLICACIONES NUMÉRICAS EN INGENIERÍA Programa de doctorado Sistemas Inteligentes y Aplicaciones Numéricas en Ingeniería TESIS DOCTORAL System Level Design Space Exploration for MPSoC: Methods, Algorithms and New Infrastructure Firma de los Directores de la Tesis Dr. D. Tomás Bautista Delgado Dr. D. Antonio Núñez Ordónez Firma del Doctorando D. Jia Li Zai Jian Jia Li Zai Jian Las Palmas de Gran Canaria, 2010 Para mi padre , mi madre y mi hermana. Sois todo lo que necesito. Agradecimientos “El maestro y el pupilo caminan juntos por el sendero del saber hasta que sus destinos les separen.” – Proverbio chino – Este proverbio chino refleja con bastante acierto el transcurrir de mi vida en estos últimos años. Lo cierto es que desde que terminé la carrera de Ingeniería de Telecomunicación, me propuse como meta personal encontrar mi sitio en el mundo. Y no me refiero solamente a un sitio donde asentar mi vida, sino también un sitio espiritual e intelectual en el que me sintiera a gusto, y en el que me pudiera dedicar profesionalmente en el día de mañana. Sin lugar a duda, mis genes y orígenes orientales han contribuido en gran medida a que tenga este tipo de reflexiones metafísicas a lo largo de mi vida. Y para encontrar este sitio que tanto ansío, empecé con este Doctorado con el fin de seguir aprendiendo y profundizando en aquellos campos que más me atrajeron durante la carrera. En este punto, doy las gracias al grupo del profesor Antonio Falcón, Cayetano Guerra y Mario Hernández por recibirme con los brazos abiertos y transmitirme sus conocimientos sobre el mundo de la visión por computador, unos conocimientos que me ha permitido conocer la complejidad del área de los Sistemas Inteligentes Autónomos en los primeros años de mi doctorado. Sin embargo, lo que yo no sabía por entonces es que mi viaje por el sendero del conocimiento me tenía preparado años más tarde una parada en la Universidad de Amsterdam. Esta estancia no sólo ha sido enriquecedora a nivel intelectual, sino también a nivel afectivo. He de reconocer que aparte de un ambiente de trabajo inmejorable, también tuve la suerte de conocer a unos buenos amigos como Andy Pimentel y Mark Thompson. De hecho, parte del mérito de esta tesis se debe en gran medida a sus dedicaciones desinteresadas y a sus enseñanzas sobre el diseño a nivel de sistema, para las cuales no encuentro palabras para expresar mi gratitud hacia ellos. Por otro lado, debo insistir en que navegar por los mares del conocimiento sin una brújula que te guía es como dar palos de ciego. Y por ello, quiero agradecer en este punto a mis directores de tesis, Tomás Bautista y Antonio Núñez, por su dedicación y su siempre disponibilidad a lo largo de estos años. Doy las gracias a Antonio por transmitirme su optimismo y alegría, así como los sabios consejos que me ha dado en estos últimos años, los cuales me han orientado en todo momento hacia la dirección que debo avanzar. Asimismo, también quiero agradecer a Tomás, quien aparte de ser uno de mis directores de tesis, ha sido un bueno amigo, y que siempre ha estado a mi lado para lo bueno y para lo malo, y especialmente le doy las gracias por ser esa farola que necesitaba en los días de oscuridad (que a propósito, no fueron pocos). Finalmente, estoy convencido de que hoy no estaría aquí si no fuese por mis seres más queridos: mi familia y mis amigos. A mis amigos les doy las gracias por sus ánimos y las palmadas en la espalda en los momentos que más lo necesitaba, los cuales también me ayudaron a ver la luz del final del túnel. Asimismo, doy las gracias a mi familia por su apoyo incondicional. Especialmente, agradezco a mi padre por su paciencia y sabiduría, a mi madre por su amor y lucha, y a mi hermana por su sacrificio y comprensión. Por último, me despido diciendo que creo firmemente en que el destino de cada persona no es algo que está fijado de antemano, sino que somos nosotros los que vamos escribiendo con nuestras acciones del día a día las páginas de la historia de nuestra vida. Y la pregunta es: ¿qué voy a escribir en la mía? “Ladies and gentlemen, Carlos has left the building”. Esta tesis ha sido financiada por el Ministerio de Ciencia y Tecnología del Gobierno de España, beca FPU AP2006-02986. Summary he increasing level of on-chip integration is leading to more complex embedded systems, which typically contain multiple storage elements, networks, I/O components, and a number of heterogeneous programmable processors for flexible application support as well as dedicated processing elements for achieving specific design goals. As a result, the system designers have to explore an exponentially growing design space in order to reach an optimal design solution considering multiple design objectives. In this context, it is widely believed that traditional design methodologies and tools are not appropriate enough to explore efficiently such a large design space, therefore coming short for designing modern SoC. In order to cope with the design complexity of such embedded systems, the working abstraction level is raised from RTL to a system level, where design space exploration (DSE) is becoming a key task of such system-level design. At the same time that the abstraction level of system design is raised to system level, an important number of system-level modelling and simulation tools emerged. However, although these tools facilitate the designers to explore a wide range of design decisions during the early design stages, these tools only provide a partial solution for the DSE process, since an overall framework and new methodologies are still needed to explore the design space in a systematic and time-efficient way. In fact, without a disciplined and renewed design methodology, system designers will still have to resort to ad-hoc techniques to perform DSE experiments. This latter is a doubtable proposition, since it severely limits the designer’s productivity and the amount of the design space that can be explored in a reasonable time. This thesis provides some novel techniques and methodologies that help addressing the above challenges, being our ultimate goals to reduce the efforts of the system designers in the design process as well as to improve the efficiency of the DSE in the early design stages. To this end, we first propose a dimension-oriented DSE methodology for coexploring multi-dimensional design spaces. The idea underlying this approach is that a large design space can be decomposed/separated in design space dimensions, such that the system designers can select different combinations of (tailored) search strategies for exploring simultaneously all dimensions of the design space, or to fix one or more of these dimensions and to focus the exploration within other dimensions. Second, we T implemented a tool to automatically generate a large variety of architecture models. Thus, it frees designers from the efforts to manually create such models, and as a result, a wide range of architectural alternatives (and consequently, a larger design space) can be easily explored. Third, we also have developed NASA infrastructure, which is a generic and modular framework to facilitate and support system-level DSE experiments. Moreover, NASA is a unified framework that allows for integrating our generator of architectural models, enables designers to incorporate different system-level simulation tools, as well as to couple different combinations of search methods (i.e., it supports our dimension-oriented DSE methodology) by means of a simple plug-in mechanism. As a result, NASA provides a flexible and re-usable environment to explore the multidimensional design spaces in a systematic and automatic way. And last, we have also proposed a hierarchical DSE methodology to address the problem of mapping a real-time application onto a target MPSoC platform. Our hierarchical approach enables designers to combine the benefits of both analytical estimation methods and system-level simulations to address the aforementioned design problem. As a result, and compared to traditional DSE methodologies using only analytical models or system-level simulators, our hierarchical DSE approach not only can explore and prune rapidly a large design space, but also can reach higher quality design solutions considering multiple design objectives in a time-efficient and accurate way. Finally, in order to demonstrate and validate the capabilities and different key properties of our approaches, several sets of DSE experiments have been illustrated in this thesis as a proof-of-concept. Apart from providing valuable feedbacks and establishing the overall directions for our future work, the results obtained in these experiments reveal that the methodologies and techniques such as the ones presented in this thesis can effectively improve the designer’s productivity as well as the efficiency of DSE at systemlevel by two orders of magnitude. Our further goal is to perform more experiments to prove and consolidate progressively the capabilities of our methodology for different application domains and an extensive range of MPSoC platforms. Index Chapter 1 Introduction.......................................................................................................................1 1.1 Systems-on-Chip design challenges..........................................................................................3 1.2 Limitations of conventional design methodologies.....................................................................5 1.3 Electronic System Level ............................................................................................................6 1.3.1 Reasons for adopting the System Level Design............................................................7 1.3.2 System Level Design.....................................................................................................8 1.4 Design space exploration at system level..................................................................................9 1.4.1 The goals of the design space exploration....................................................................9 1.4.2 Components of the design space exploration ...............................................................9 1.5 Contributions of the thesis .......................................................................................................13 1.6 Thesis structure .......................................................................................................................15 Chapter 2 CASSE: a SystemC-based modelling and simulation tool.........................................17 2.1 System-level simulation tools and Open SystemC Initiative standards....................................19 2.1.1 IEEE 1666 SystemC standard.....................................................................................19 2.1.2 OSCI TLM 2.0 standard ..............................................................................................20 2.2 Related work............................................................................................................................20 2.3 CASSE design flow and internal structure...............................................................................22 2.3.1 CASSE methodology and design flow.........................................................................24 2.3.2 CASSE tool structure ..................................................................................................31 2.4 Real-time visual tracking system case study ...........................................................................32 2.4.1 Computer vision system and the real-time tracking algorithm.....................................32 2.4.2 Experimental results....................................................................................................34 2.5 Conclusions.............................................................................................................................39 Chapter 3 Methodology and infrastructure for multidimensional DSE.......................................41 3.1 Introduction..............................................................................................................................43 3.1.1 Design space dimension .............................................................................................43 3.1.2 Generic infrastructure for multidimensional DSE.........................................................44 3.2 Related work............................................................................................................................46 3.3 Preliminaries and definitions....................................................................................................48 3.4 Overview of the NASA framework ...........................................................................................50 3.5 Implementation of NASA .........................................................................................................53 3.5.1 Interfaces ....................................................................................................................53 3.5.2 Search module and dimension-oriented co-exploration ..............................................55 3.5.3 Feasibility checker.......................................................................................................57 3.5.4 Architectural platform generator..................................................................................59 3.5.5 Translator....................................................................................................................62 3.5.6 Simulator.....................................................................................................................63 3.5.7 Evaluator.....................................................................................................................64 3.6 Experimental results ................................................................................................................65 3.6.1 NASA configurations for experiments and parameter settings....................................65 3.6.2 DSE behaviour and sensitivity to various parameter settings......................................68 3.6.3 Hierarchical refinement and analysis of 2D-DSE with NASA ......................................76 3.7 Conclusions.............................................................................................................................79 Chapter 4 Strategy and algorithms for mapping real-time application onto MPSoC ................81 4.1 Introduction ..............................................................................................................................83 4.1.1 Complexity of the application mapping on MPSoC......................................................83 4.1.2 Multi-objective optimization problem............................................................................83 4.1.3 Existing strategies for exploring the design space of mapping....................................85 4.1.4 Hierarchical DSE methodology....................................................................................87 4.2 Related work............................................................................................................................88 4.3 Preliminaries and problem statement.......................................................................................90 4.4 Overview of our hierarchical DSE methodology.......................................................................94 4.5 Heuristics-based algorithms and analytical model for hierarchical DSE ..................................95 4.5.1 Static performance estimation.....................................................................................96 4.5.2 Potential solutions .....................................................................................................105 4.5.3 Global system simulation...........................................................................................106 4.6 Experimental results ..............................................................................................................107 4.6.1 Analysis of the DSE efficiency...................................................................................107 4.6.2 Analysis of the quality of the optimal solutions ..........................................................111 4.7 Conclusions ...........................................................................................................................113 Chapter 5 Conclusions and future work.......................................................................................115 5.1 Conclusions ...........................................................................................................................117 5.2 Future work............................................................................................................................120 Chapter 6 Resumen en español ....................................................................................................123 6.1 Introducción ...........................................................................................................................126 6.1.1 Diseño a nivel de sistema..........................................................................................127 6.1.2 Exploración del espacio de diseño a nivel de sistema...............................................130 6.1.3 Contribuciones de la tesis .........................................................................................134 6.1.4 Estructura de la tesis.................................................................................................136 6.2 CASSE: entorno de modelado y simulación a nivel de sistema.............................................138 6.2.1 Introducción...............................................................................................................138 6.2.2 Herramientas de simulación a nivel de sistema basadas en SystemC......................139 6.2.3 Flujo de diseño e implementación interna de CASSE ...............................................139 6.2.4 Caso de estudio: sistema de seguimiento visual.......................................................144 6.2.5 Conclusiones.............................................................................................................149 6.3 Metodología e infraestructura para la exploración del espacio de diseño multidimensional ..150 6.3.1 Introducción...............................................................................................................150 6.3.2 Implementación de NASA .........................................................................................152 6.3.3 Conclusiones.............................................................................................................161 6.4 Estrategias y algoritmos para el mapeo de aplicaciones en MPSoC.....................................163 6.4.1 Introducción...............................................................................................................163 6.4.2 Problema de optimización multiobjetivo ....................................................................163 6.4.3 Estrategias actuales para la DSE..............................................................................165 6.4.4 Metodología de DSE jerárquica.................................................................................167 6.4.5 Algoritmos y modelo de estimación para la metodología de DSE jerárquica ............168 6.4.6 Conclusiones.............................................................................................................172 6.5 Conclusiones y trabajo futuro.................................................................................................174 6.5.1 Conclusiones obtenidas ............................................................................................174 6.5.2 El trabajo futuro.........................................................................................................176 References 177 Index of figures Fig. 1. 1 Relationship between the components of the system-level DSE. ...................... 10 Fig. 2. 1 CASSE design flow............................................................................................. 25 Fig. 2. 2 Example of task file............................................................................................. 26 Fig. 2. 3 Example of task-graph description file................................................................ 26 Fig. 2. 4 Parallelization process of the application in the task graph................................ 27 Fig. 2. 5 Example of architectural description file. ............................................................ 28 Fig. 2. 6 Example of mapping description file................................................................... 29 Fig. 2. 7 CASSE internal structure.................................................................................... 31 Fig. 2. 8 Pattern extraction operation and resulting distortion surface. ............................ 33 Fig. 2. 9 Tasks graph description of our tracking system. ................................................ 34 Fig. 2. 10 Architecture model used for the multiprocessor solution analysis.................... 35 Fig. 2. 11 Achievable performance with different parameter configurations for PE 2. ..... 36 Fig. 2. 12 Synchronization bytes for each port of PE to process 125 frames................... 37 Fig. 2. 13 Total synchronization load generated by different mapping solutions.............. 38 Fig. 2. 14 Tracking system performance with other applications running on the target MPSoC platform................................................................................................................ 39 Fig. 3. 1 An example of the classification of design options in design space dimensions. .......................................................................................................................................... 43 Fig. 3. 2 The NASA infrastructure..................................................................................... 51 Fig. 3. 3 Search Algorithms (SA) and search strings in NASA......................................... 54 Fig. 3. 4 Different techniques to link design decisions in a single design point................ 57 Fig. 3. 5 Example of a BTU generation and element container........................................ 59 Fig. 3. 6 Example of 2D and 3D meta-platform generation. ............................................. 60 Fig. 3. 7 Platform instance generation and platform string checking................................ 61 Fig. 3. 8 Example of architecture instance generation process........................................ 62 Fig. 3. 9 Plug-in examples for generating architectural model in Sesame and CASSE... 63 Fig. 3. 10 DSE results for four NASA configurations. ....................................................... 69 Fig. 3. 11 Average percentage of feasible, repaired and infeasible design points per iteration in our DSE experiments. ..................................................................................... 71 Fig. 3. 12 Average fitness values per iterations................................................................ 72 Fig. 3. 13 Incremental diversity per iterations................................................................... 73 Fig. 3. 14 Explored design points by each selected NASA configuration......................... 74 Fig. 3. 15 Examples of design points found by DSE with pc=0.8, pm=0.3 after 40 iterations............................................................................................................................ 75 Fig. 3. 16 Target platform template for the second set of experiments. ........................... 77 Fig. 3. 17 Comparative results obtained in the second set of DSE experiments.............. 78 Fig. 3. 18 Example of NASA output. ................................................................................. 79 Fig. 4. 1 Example of pruning the design space of mapping.............................................. 86 Fig. 4. 2 Overview of the hierarchical DSE methodology. ................................................ 95 Fig. 4. 3 Example of the HW/SW partitioning algorithm.................................................... 96 Fig. 4. 4 Example of the tasks clustering algorithms. ....................................................... 99 Fig. 4. 5 Example of the cluster assignment algorithm and analytical estimation. ......... 104 Fig. 4. 6 Example of mapping solution description strings..............................................105 Fig. 4. 7 Target architecture template and component configuration parameters.......... 108 Fig. 4. 8 Results obtained in GA-based DSE experiments.............................................110 CHAPTER 1 5 In this point, we wonder whether the established methodologies and tools (and/or current ad-hoc approaches) for systems design are appropriate enough to meet these challenges. Without a disciplined design methodology, however, system designers will have to resort to ad-hoc techniques to implement concurrent applications on complex MPSoC platforms, which is doubtful proposition. We believe that new design methodologies and engineering practices are necessary for the design of complex MPSoC to achieve the productivity and efficiency that has already been reached for single processor systems. 1.2 Limitations of conventional design methodologies It is now widely believed that traditional design methodologies come short for designing the modern SoCs due to following reasons [4, 12]: • A classical design methodology often starts from a single application specification, making it inflexible for broader exercises. HW/SW co-design could represent an example of such a classical design methodology. Typically, HW/SW co-design methods start from a single system specification that is gradually refined and synthesized into an architecture implementation. This architecture implementation is usually built with programmable processors and/or dedicated hardware components. However, the major disadvantage of this approach is that it forces the system designer to make early decisions on the HW/SW partitioning of the system – that is to identify, at a very early stage, parts of the system which will be implemented in hardware and software, which only makes sense if the right HW/SW partition is known beforehand. • The co-simulation frameworks that model the classical HW/SW co-design approach, generally combine low (low-level) simulators, one for simulating the programmable components running the software and another for the dedicated hardware. The common practice is to employ instruction-level simulators for the software part, while the hardware part is usually simulated at RTL level using a hardware description language like VHDL or Verilog. Building these detailed simulation models for the hardware part requires significant effort, making them impractical in the early design stages. Moreover, these low level simulators usually have low simulation speeds what hinders fast exploration of the design space. INTRODUCTION 6 On the other hand, such tools often limit the size and complexity of the systems due to the enormous amount of details the designer has to handle, which obscure the system-wide view and slows the simulation of the design model considerably. Using this low productivity approach, designers occasionally settle for whatever works rather than designing what works best — and risk launching an uncompetitive product. • Most of the design decisions are made in a very early design phase, and since they cannot be validated until very late, wrong decisions have an enormous impact on the success or failure of the final design. For example, architecture decisions as well as the best partitioning of the application functionality are taken during this phase using static techniques (e.g., spreadsheets) or just based on the expertise of the system designer. Unfortunately, these techniques are not suitable enough to deal with the complexity of new designs. Static techniques cannot capture the complex use cases and interactions of the applications running on the designs nor their dynamic behaviour. • The HW/SW integration cannot be performed until the HW platform is available, which happens too late in the classical design flow. The main problem is that functional and non-functional mismatches with the specification cannot be detected until the simulation of the complete system is not executed. Moreover, as new SoCs become heterogeneous multiprocessors with an important amount of SW running on them, the HW/SW interactions are also more complex, and the chance for a first-time working design is very low. 1.3 Electronic System Level In order to overcome the aforementioned shortcomings of the classical design methodology, System Level Design (SLD) methods have been proposed by the embedded system design community as a complement to the traditional methods, as well as to improve the productivity of the system designers. A complete overview of the SLD field can be seen in [5, 6]. In the literature SLD is also referred as ESL “Electronic System Level”, being design included in this expression. CHAPTER 1 7 1.3.1 Reasons for adopting the System Level Design Roughly speaking, SLD has been focused mainly in three key aspects: (i) higher abstraction level: moving designers towards higher abstraction levels above RTL, (ii) separation of concerns: separating the various aspects of the design to allow a more effective exploration of alternative solutions, and (iii) refinement: allowing the progressive refinement of the system from abstract descriptions down to implementation. Higher abstraction levels Like the designer’s abstraction level moved from standard-cells design (using full-custom techniques) to the RTL (using hardware description languages, that is, HDLs) in the 90’s, nowadays new design methods propose to elevate the designer’s abstraction level from RTL to system level. At the system level, the basic elements are of a bigger granularity such as Intellectual Property (IP) blocks or complete subsystems, which are described using high-level modelling languages such as SystemC [7, 8], SpecC [9], SystemVerilog [10] and ArchC [11]. This means that SLD develops SoCs and verifies its behaviour in terms of high-level block input and output events, and inter-block data transfers at the transaction level. The elimination of so many implementation details: - simplifies the design effort, since new (or derivative) design can be obtained by maintaining the SoC platform and enhancing and/or adding specific features in an easier way than if using a lower abstraction level. - speeds up the simulation time, allowing system-level simulations to execute more than 1,000 times faster than RTL [12]. - allows the system designer a direct and clear view of system behaviour and design attributes relevant to the system design. Separation of concerns Separating the various aspects of the design problem beyond hardware and software is a key issue in SLD in order to overcome the limitations of conventional design methods. The concepts of orthogonalization of concerns [13], interface-based design [14], and the Y-Chart approach [15] have established the basis to provide such separation in SoC design. All these approaches facilitate a more effective exploration of alternative designs, as will be explained later in Section 1.4. Refinement Once the system designer had found an optimal system design at system level, the model of this design can be used as an "executable specification" that drives the entire INTRODUCTION 8 subsequent RTL implementation, i.e., replacing each system-level component with another one at RTL, for example. This way, progressively refining a design from a higher abstraction level down to a lower abstraction level is a clear strategy to reduce the complexity of the design process [16]. Although such refinement process can be performed manually, real benefit comes when the process is automated via tools. Examples of this latter are the high-level synthesis tools that automatically transform a C description into an RTL implementation [17], or the code generation tools that create C or C++ code from UML descriptions. 1.3.2 System Level Design In the last decades, several SLD approaches have been proposed taking into account the above mentioned aspects. These approaches can be broadly categorized into the following three groups: • Component-based design (CBD). It follows a bottom-up design approach, where complete architectures are built up assembling together pre-designed components. These components are interconnected and communicate each other by automatically inserting wrappers among them [18], or by using standard interfaces and bus protocols. • System-level synthesis (SLS). This approach moves the designers towards working at a higher abstraction level, where the starting point is a behavioural description of the system [19, 20]. SLS follows a top-down design flow, where the architecture is generated from that behavioural description by gradually adding implementation details until the final implementation is reached. • Platform-based design (PBD). PBD [13] is a meet-in-the-middle design approach, i.e., it combines a bottom-up approach for creating a predefined architectural platform, and a top-down approach to map the system behaviour onto the components of the architecture. This way, a common architectural platform can be specified and shared by multiple applications (inside a particular application domain). Moreover, PBD promotes the reuse of IP blocks for the purpose of increasing productivity and reducing manufacturing costs for high production volumes. CHAPTER 1 9 1.4 Design space exploration at system level 1.4.1 The goals of the design space exploration Harnessing the benefits of working at system level, Design Space Exploration (DSE) is becoming a key task of SLD. In this context, a design space is composed of a set of design points, where each of them represents a system design with different design decisions, concerning HW/SW partitioning, platform topology, resources allocation in the architecture, number and type of architectural components, mapping of the application functionality on the architecture, and so on. This way, the ultimate goal of the systemlevel DSE is to explore such design space (i.e., search and select among somehow different design points from the design space) in a time and effort efficient way during the early design stages, and analyse each candidate in terms of its system-wide metrics (e.g., performance, cost/area and power consumption) in order to achieve the best design solution1 (or a set of optimal solutions) that satisfy a set of design constraints or objectives imposed by the designer. Evidently, it is worth to mention that the more design decisions (or options), the larger the resulting design space (or the more possible design points) is, and the more effort and time is needed to carry out the DSE. On the other hand, besides exploring a wide range of design options, DSE also facilitates the system designers to detect the impact of different design decisions on the global system behaviour, and make optimization decision prior to completion of prototype hardware. Therefore, such early DSE is of paramount importance, as early design choices heavily influence the success or failure of the final product, and can avoid wasting time and effort in further design steps without the possibility of meeting design requirements because of the inappropriate choices of design decisions. 1.4.2 Components of the design space exploration The process of system-level DSE logically consists of three interdependent components: (i) the search method to systematically travel through the design space, (ii) the evaluation technique to assess the quality (in terms of system-wide metrics) of each design point selected by the search method, and (iii) a mechanism to generate the system description that is used by the evaluation technique to provide the needed system-wide metrics. The resulting relationship between these three components is shown in Fig. 1.1. 1 In this document, the terms “design solution”, “candidate”, “design point” and “system design” are used interchangeably. INTRODUCTION 10 Fig. 1. 1 Relationship between the components of the system-level DSE. 1.4.2.1 The search methods Two categories of search methods for DSE can be distinguished [21]: strategies for covering the design space and methods for pruning the design space. It should be noticed that both categories are not strictly orthogonal to each other. In fact, Chapter 4 presents a methodology for system-level DSE which combines techniques belonging to both categories in order to improve the efficiency of DSE (in terms of run time), as will be explained later. Strategies for covering the design space Three kinds of strategies can be mentioned here: exhaustive, random, and guided search. While the two first techniques are often implemented in a control script customized for every DSE experiment, which makes them inflexible and hardly reusable, the guided search relies typically on heuristics. • Exhaustively evaluating every possible design point. This straightforward approach evaluates every possible combination of design parameters, so it is prohibitive for large design spaces. Although the design space can be reduced by limiting the range of design parameters, the search process is completely unguided and unbiased with respect to the preferences of the designer. Examples of design systems and case studies based on exhaustive search can be widely found in the literature [22-32]. • Randomly sampling the design space. Evaluating only random samples is the obvious choice to cope with large design spaces. It also has the advantage of Evaluation technique Performace, power, cost… Generator of system description A pp lication model Architecture model Mapping model System model Search method Design s p ace Design points descriptions System metrics User specifications DSE infrastructure CHAPTER 1 11 revealing an unbiased view of the characteristics of the design space. Monte-Carlo algorithm [33] and simulated annealing [34] are some techniques that can be clustered in this group. • Incorporating knowledge of the design space. Search strategies in this category try to improve the convergence behaviour towards optimal solutions by incorporating knowledge of characteristics of the design space into the search process. The knowledge may be updated with every iteration of the search process or may be an inherent characteristic of the search algorithm itself. Hill climbing algorithms [35] and evolutionary algorithms [36-45] are the most representative examples for this group of search strategy. Methods for pruning the design space All mentioned exploration methods can be employed with the techniques presented in this subsection to reduce the complexity of the search by pruning the design space. • Hierarchical exploration. Starting with a coarse problem statement, interesting regions of the design space are identified and ranked. Typically, this last process is focused on eliminating rapidly design points that cannot satisfy design specifications, rather than a detailed evaluation of each design alternative. Subsequently, a set of candidate solutions (selected by the previous process) is evaluated in more detail [23, 46-48]. • Subsampling of the design space. Subsampling the design space is a reasonable choice if the designer is interested in an unbiased exploration, where an exhaustive search would be prohibitive. The subsampling pattern could be completely random, based on some regular grid, or biased by some expected shape of the design space and/or objective function. The Monte-Carlo technique, the simulated annealing algorithm and evolutionary algorithms can be considered as examples for this kind of techniques. 1.4.2.2 The evaluation techniques During the system-level DSE, two kinds of techniques can be used to evaluate a single design point or system design: system-level simulation-based evaluation and analytical estimation approaches. INTRODUCTION 12 System-level simulation-based evaluation System-level simulations are particularly well suited to investigate dynamic, sporadic, and/or unforeseeable effects in the system, such as the contention delays due to simultaneous access requested by multiple competing PEs. While an analytical model can be too pessimistic since these models often consider the worst-case estimation time (WCET) only, simulations may reveal more realistic results for average-case optimization. A review of these tools can be found in Chapter 2 of this thesis. Analytical estimation approaches Analytical estimation methods come into play if deterministic behaviour or WCET is a reasonable assumption for the system under evaluation. While simulation-based evaluation might be too time-consuming (even working at system-level), analytical models ease early design decisions by identifying corner cases of potential designs, which often are difficult to detect due to the overall complexity of modern SoCs. Nevertheless, the main drawback of this analytical approach in our point of view, is still the lack of accuracy in the estimation/evaluation. A review of the analytical estimation approaches can be found in Chapter 4 of this thesis. 1.4.2.3 The generator of the system description Independently on the nature of the evaluation techniques (i.e., simulation or analytical model), a complete system model should be created first in order to evaluate appropriately each design point of the design space. This latter becomes a requirement for the case of simulation-based evaluation. In these cases, in order to perform the simulation and to obtain system-wide metrics, these tools typically require an executable system model (ESM), which can be considered as a virtual-model or meta-model of the system implementation that include not only information about the application functionality and details about the architecture, but also specify how both domains are related together. The separation of concerns and the Y-Chart principle facilitate enormously the conception and creation of such ESM. According to these approaches, a system (and in our case, an ESM) can be specified with the combination of three models: an application model, an architecture model and a mapping model. The latter means that Y-Chart principle decouples application from architecture by recognizing distinct models for them. An application model – derived from a target application domain – describes the functional behaviour of the application (using, e.g., Kahn Process Networks (KPN) or task-graphs) in an architecture-independent manner. Simultaneously, an architecture model –defined CHAPTER 1 13 with the application in mind– specifies the architecture implementation (by means of highly configurable predefined components provided typically by the tool library) and captures their performance constraints. Finally, an explicit step (or model) maps the application model onto an architecture model for co-simulation, after which distinct system metrics can be quantitatively evaluated. An ESM created in this manner presents several benefits when compared with other traditional solutions (e.g., emulators, FPGA or RTL simulations): • An ESM can be earlier available. This is an implicit consequence of working at a higher abstraction level than RTL, which implies fewer implementation details, and therefore can be created with less effort. • An ESM is a more flexible solution. Since these meta-models of system implementation contain fewer details and are built in a compositional way, changes can be done quicker and new models can be derived in a shorter time than with other traditional solutions. Finally, we would like to notice that such ESMs can be created manually [49] or automatically [50]. However, this manual creation process (and set up of this model) can be a very error-prone, time-consuming and labour-intensive task for the system designer, while the automation of this process could improve significantly the design productivity and the DSE efficiency. An approach for generating automatically an ESM will be discussed in Chapter 3. 1.5 Contributions of the thesis This thesis is focused on the methodologies and techniques for performing efficient MPSoC design space exploration at system level. More specifically, we have developed new methods, algorithms and infrastructure/support to deal with the design’s complexity of modern SoCs that the system designers have to face in DSE during the early design stages. The main contributions of this thesis are: • We propose a new and generic system-level MPSoC design space exploration infrastructure, called NASA (Non Ad-hoc Search Algorithm). This highly modular framework uses a set of well-defined interfaces to easily integrate different search INTRODUCTION 14 strategies as well as existing system-level simulation tools in a single environment in a simple plug-and-play fashion. As a result, the potentials for reuse of the framework are significantly increased since each DSE experiment can be performed without the need of preparing experiment-customized scripts, but it only requires a simple change of the user’s input constraints values. • We have implemented a new approach to gradually and automatically generate an ESM that is simulated for obtaining system metrics to evaluate design decisions. Thus, the entire DSE process (composed of search, ESM generation and design point evaluation) is performed in an automatic and systematic fashion. This improves design productivity and decreases the designer’s efforts. • We have developed a novel methodology for system-level MPSoC DSE called dimension-oriented DSE approach. According to our approach, a large design space is explicitly separated into dimensions, which could represent design decisions that are orthogonal to each other such as mapping, architectural components, and platform. Thus, the designer can choose to simultaneously explore all dimensions, or to fix one or more of these dimensions and to focus the exploration within other dimensions. This means that the designers should have to configure the appropriate number of (possibly different) search algorithms to simultaneously co-explore the various design space dimensions. • We have proposed a new heuristic-based method, which is capable of taking into account multiple design objectives that handles the problem of the real-time application mapping onto a flexible MPSoC platform. Moreover, this analytical approach can evaluate a design point considering both static and dynamic system behaviours. This analytical approach forms part of a hierarchical DSE approach, where our analytical approach relies on a rough estimation to eliminate rapidly a large number of design points in the pruning phase, while only a small number of candidate mappings are evaluated accurately by a system-level simulator in the exploration phase. Our experimental results reveal that this hierarchical DSE approach can improve significantly the DSE efficiency as well as achieve good quality solutions. CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 22 abstraction levels. These simulators range from high-level system simulators (e.g., MatLab and SystemC to verify the application behaviour) to cycle-accurate instruction set simulators (ISS) such as SimpleScalar [69]. On the other hand, Metropolis [67] targets at integrating modelling, simulation, synthesis, and verification tools within a single framework. It makes use of the concept of metamodel, which offers syntactic and semantics mechanisms to support functionality capture and analysis, as well as architecture description and mapping of functionality to architectural elements. Besides the function/architecture separation, Metropolis also proposes the separation between the capabilities of an architectural model versus the cost it bears when it implements a given behaviour. That is, architectural components are driven by events which are annotated with the costs of interest such as the energy or time for execution. Although quite valuable and innovative from the methodological point of view, this framework is not based on SystemC. This is an important drawback for their interoperability and integration with typical system-level design flows adopted in the industry. An existing SystemC-based framework that applies similar design methodology than CASSE is presented in [61]. Kogel et al. [61] presents a Virtual Architecture Mapping methodology that enables the quantitative evaluation of an application-to-architecture mapping by means of an executable performance model. Shared processing resources are modelled via the Virtual Processing Unit that allows the spatial mapping and execution of multiple tasks on a single element. Similar to CASSE, this framework accelerates the exploration of a large design space by means of description files where individual timing annotations as well as the mapping are specified. Unlike CASSE, on the other hand, they use communication channels to capture timing aspect. That is, the channels provide methods to annotate processing delay and initiation interval, while in CASSE, the timing information is annotated into the tasks and the communication channels are used to exchange shared data/tokens and to synchronize status of the channel, as will be explained in Section 2.3.1. 2.3 CASSE design flow and internal structure CASSE [12, 79, 91] is a SystemC-based modelling and simulation environment, which aims to help the system designers to explore and analyse application models running on an early available architecture model under a unified environment. CASSE has been CHAPTER 2 23 developed at Research Institute for Applied Microelectronics (IUMA) of ULPGC and the main key properties taken into account during its development are: • Application modelling and mapping. During the specification phase, it is very unlikely that the application is available in its final stage (e.g., embedded software and/or hardware implementation). Therefore, other techniques should be applied that allow modelling and setting the application requirements in a more abstract way. Moreover, to allow an extensive DSE, separation of concerns has also to be applied. This means that the behaviour, interfaces and cost (e.g., timing information) of the applications are modelled in an orthogonal way and merged once the application is mapped on the targeted architecture. • A library of highly configurable generic architecture components. During the specification phase, distinct architectures with different properties need to be explored. In order to have an ESM early during the specification phase, IP models have to be quickly available and therefore the effort to create and assemble them has to be minimal. As a solution to this limitation, a library of highly configurable generic component models, emulating the common functionality and timing of several IP types, has to be put in place. Such generic IP models can be used when the model for the specific IP is not available yet. Moreover, these generic component models have to support the mapping of application models onto them. • Advanced performance analysis. During system-level simulations, tons of different performance data has to be interpreted and analysed before deciding whether a system instance fulfil the imposed requirements or not. Pruning this big amount of information in order to find performance bottlenecks and possible optimizations is not a trivial task in the design of modern SoCs. Therefore, new performance analysis techniques allow identifying hot spots and bottlenecks in a complex design and easily correlate them with the application model. This enables an easier and faster way to isolate and hence optimize the designs. • Short set-up time, fast simulation and relative accuracy. For evaluating a single design point, an ESM needs to be created, configured, simulated, and the obtained results analysed in a short time. The shorter this process, the bigger number of different design alternatives that can be explored. More specifically, the requirements are: CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 24 o Small effort to configure/set up the ESM. User-friendly front-end tools and possibly some scripting capabilities are required to enable quick modifications in the ESM. o Fast simulations. At least an improvement factor of x1000 compared to RTL simulations is required to perform meaningful simulations during the DSE. This leads us to simulation speeds in the range of several MHz. o Relative accuracy. Although the highest accuracy (compared with RTL simulations) is always desired, very often certain level of accuracy can be traded in order to reduce the modelling effort and improve the simulation speed. For exploration purposes, the concept of relative accuracy or fidelity is introduced, so that the ESM can be used to evaluate, for instance, whether a system instance in particular is better or worse than another one for certain aspects. 2.3.1 CASSE methodology and design flow Considering the aforementioned properties, CASSE is implemented following the Y-Chart principle, where the application functionality and the architecture are independently modelled and combined in a separate mapping phase (see Fig. 2.1). Quantitative information about the system execution is then obtained by means of simulations. The tool can be used to perform functional simulations of the application model only or performance simulations of the application mapped and executing on the architectural model. After simulations, the obtained information can be visualized and analysed in order to guide further optimizations in architecture, application and/or mapping structure. CASSE controls all stages in the design flow by means of textual description files. These description files are read and parsed by the tool during elaboration time in order to create and properly configure the desired system model. The result is a model (i.e., ESM) that is executed using the SystemC kernel. Hence, the tool simplifies the exploration of several design points by means of these description files that can be easily modified in order to create a new system instance. Since changing the description files does not require recompiling the existing models, extensive parameters sweeps can be performed easily using scripts. Application modelling. CASSE applies a parallel programming model based on the Task Transaction Level (TTL) interface [74]. According to the TTL specification, an application is described as a process network where parallel tasks communicate with CHAPTER 2 25 each other by means of unidirectional channels. A task is an entity that performs computations. Tasks are connected to channels via ports, and they communicate and synchronize with each other by calling TTL interface primitives on their ports. Hence, TTL provides a fair separation between computation and communication at the application level. TTL can be used both for developing parallel application models and as a platform interface for integrating hardware and software modules on a platform infrastructure. A good point of TTL is that it only defines the interface primitives and their functionality, but leaves their implementation open to the designer. Fig. 2. 1 CASSE design flow. In the tool, tasks containing the application functionality are written in C/C++ (i.e. the functionality per task is fixed at compile time). However, the network structure (i.e. port to channel connections) and its configuration (e.g. data/token size) are described in a separate text file. The tool uses this description file to instantiate and bind together tasks and channels creating an executable model of the network. This architecture-independent executable model can be simulated using CASSE in order to validate the functional correctness of the application. An example of a task file and another of a task-graph description file are shown in Fig. 2.2 and Fig. 2.3, respectively. During this stage, we however would like to point out that the main drawback of CASSE is the parallelization process of the application source code in a task graph. In fact, as illustrated in Fig. 2.4, current CASSE version provides no mechanism to carry out automatically such process, on the contrary, the system designers have to perform CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 26 manually this task. Basically, this latter means that the designers should have to rely on their intuitions and/or experiences to adapt the source code, i.e., split the application in a set of tasks and incorporate appropriately the corresponding TTL interface primitive calls inside each task. Fig. 2. 2 Example of task file. Fig. 2. 3 Example of task-graph description file. The correct decomposition of the application is very important due to several reasons. On one hand, this way we can determine the order of the execution of tasks, their degree of dependence and the exact data that must be communicated between different tasks. This latter determines the exact communication data granularity and influences further // task file #include “task.h" … // constructor task_name::constructor(const char* nm) :task_if(nm) { } int task_name::mapPorts() { CASSE_BIND_PORT_ON; CASSE_BIND_PORT(OUTPORT,sizeof(token_size)); CASSE_BIND_PORT(INPORT,sizeof(token_size)); CASSE_BIND_PORT_OFF; } void task_name::main() { … // Source code in C++ // including TTL interface primitive calls (i.e., read/write channels) … } // Task-graph description file # Tasks creation # .CREATE -TASK task_1 -N_PORT number_of_ports ; .CREATE -TASK task_2 -N_PORT number_of_ports ; … .CREATE -TASK task_id -N_PORT number_of_ports ; # Channels creation # .CREATE –CHANNEL channel_1 -SIZE number_of_tokens -TSIZE token_size ; .CREATE -CHANNEL channel_2 -SIZE number_of_tokens -TSIZE token_size ; … .CREATE -CHANNEL channel_id -SIZE number_of_tokens -TSIZE token_size ; # binding part # .BIND -TASK task_id -PORT port_id TO -CHANNEL channel_id -PRODUCER ; … .BIND -TASK task_id -PORT port_id TO -CHANNEL channel_id -CONSUMER ; … CHAPTER 2 27 performance communication analysis. On the other hand, with this decomposition the number of communication points and channels on the system can be determined, and the sending points for producers and the receiving points for consumers in each task entity can be more clearly identified. Fig. 2. 4 Parallelization process of the application in the task graph. From our point of view, such manual code transformation process is not efficient neither viable for large and complex applications, besides it can be an error-prone and timeconsuming task. Although some techniques/algorithms can be developed and integrated in CASSE to automate this process (e.g., generator of KPN used in [75, 76]), this latter is not addressed in this thesis, but it is proposed as future work to extend CASSE capabilities. Architectural modelling. CASSE provides easy and fast architectural modelling by describing a system as a modular composition of highly configurable predefined elements (provided by the tool libraries). The library of predefined elements is composed of processing elements (PEs), storage elements (SEs), and network elements (NEs). PEs model generic multitasking computational units, which include an abstract task scheduler model that supports different arbitration schemes and advanced features like interrupts and pre-emption. SEs model generic multi-port memory elements. Finally, NEs model generic shared bus interconnections including programmable arbiters, address decoders, and optional input buffers. All predefined elements are connected together in a plug-andplay fashion by means of the Inter-Component Communication Protocol (ICCP) interface. ICCP is an abstract communication protocol, which defines a point-to-point interface and a group of communication primitives between two entities named Initiator and Target. Task 1 Application source code … Task N Task 2 Manual process Task 2 Task 1 Task 3 Tas k 4 … … … Split an application in tasks Insert TTL interface primitive calls CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 28 Both the ICCP interface and the library of predefined elements have been developed using SystemC and the TLM Standard library. A separate description file is used in order to specify the architectural composition of the system (i.e., number of elements of each type, number of interfaces per element, and their interconnections), and its configuration (e.g. memory map, memory sizes, communication latencies per interface, task scheduler policy, etc.). An example of the architectural description file is shown in Fig. 2.5. Fig. 2. 5 Example of architectural description file. Mapping and execution. One of the main advantages of the tool as a unified environment is the straightforward mapping support of the application functionality onto the modelled architecture. That is, CASSE supports the direct mapping of the TTL applications (i.e., tasks and channels) onto the architectural models, and the execution of the resulting system with no need for source code changes (i.e., the original source code of the tasks is executed directly in the architectural model). This technique is called Host Code Emulation (HCE). HCE avoids the usage of accurate hardware models and ISS models and, therefore, reduces the modelling effort and allows faster simulations. // Architectural description file .CREATE -CLOCK clock_domain_1 -PERIOD 5 -UNIT SC_NS ; .CREATE -CLOCK clock_domain_2 -PERIOD 15 -UNIT SC_PS ; … .CREATE -PROCESSING PE_name -N_INIT number_of_initiators ; // latency parameters .CONFIGURE -PROCESSING PE_name -INIT init_id -WIDTH 32 -LAT 1 1 1 0 -CONNID PE_id ; // Tasks Scheduler parameters .CONFIGURE -PROCESSING PE_name -TS MLQ 100 50 0 ; .CONFIGURE -PROCESSING PE_name -PTW YIELD 20 20 10 20 ; … .CREATE -STORAGE SE_name -N_TARGET number_of_targets ; .CONFIGURE -STORAGE SE_name –SIZE SE_size ; .CONFIGURE -STORAGE SE_name -TARGET 0 -WIDTH 32 -LAT 0 1 1 ; … .CREATE -NETWORK bridge_id -N_INPUT number_of_inputs -N_OUTPUT number_of_outputs ; .CONFIGURE -NETWORK bridge_id -WIDTH 32 -BUFFERED y -I_LAT 1 1 1 -O_LAT 1 1 1 0 ; .CONFIGURE -NETWORK bridge_id -OUTPUT_B 0 -RANGE 0x00000000 0xffffffff ; … .CREATE -NETWORK NE_id -N_INPUT number_of_inputs -N_OUTPUT number_of_outputs ; .CONFIGURE -NETWORK NE_id -WIDTH 32 -BUFFERED n -I_LAT 0 0 0 -O_LAT 0 0 0 0 ; //Arbiter policy .CONFIGURE -NETWORK NE_id -ARBITER ROUNDROBIN ; .CONFIGURE -NETWORK NE_id -OUTPUT 0 -RANGE 0x00000000 0x0003ffff ; … .CREATE -LINK link_id -WIDTH 32 ; … .BIND -CLOCK clock_domain_1 TO -PROCESSING PE_name ; .BIND -CLOCK clock_domain_1 TO -STORAGE SE_name -TARGET target_id ; … .BIND -CLOCK clock_domain_2 TO -NETWORK NE_id -INPUT ; .BIND -CLOCK clock_domain_2 TO -NETWORK bridge_id -OUTPUT ; … .BIND -LINK link_id TO -PROCESSING PE_name -INIT PE_id ; … // Configuration of memory map .CONFIGURE -MEMAREA map_id -SIZE SE_size INTO -STORAGE SE_name -BASE map_range ADDRESS 0 ; CHAPTER 2 29 Nonetheless, timing delays reflecting the computational costs of the functionality has to be annotated into the tasks. This can be performed by either automatic methods like those described in [77, 78] or the timing information has to be extracted and annotated by hand. Fig. 2. 6 Example of mapping description file. Like for the previous steps, another description file is used for the tool in order to control the mapping procedure. An example of such mapping description file can be seen in Fig. 2.6. The outcome of the mapping stage is an executable model containing the selected application/architecture instance. This executable model can be executed using the SystemC kernel in order to validate both the functional correctness and the performance of the system modelled. At this point we would like to stress that, the current version of CASSE provides unfortunately no automated mechanism to facilitate the mapping of the application models (i.e., tasks and channels) onto the architecture models, but such a mapping process is carried out manually by designers. That means that the designers have to make explicitly the correct mapping decisions in order to achieve a feasible mapping. To this end, CASSE can ensure a feasible and dead-lock free mapping following the next two steps. First, TTL tasks should be mapped onto available PEs of the architectural model. Second, if two communicating TTL tasks are mapped onto different PEs, the TTL channel associated to those TTL tasks should be mapped onto available SEs of the architectural model such that the aforementioned PEs can access to these SEs. This latter is an important feature to warrant a feasible mapping, since all the exchanged data (or token) and synchronization information are contained in these channels. In fact, TTL channels are composed of two parts: the channel buffer (CHB) and the channel administration table (CHAT). The CHB, where the data/token is stored, is unique for the producer and for all the consumer tasks connected to it. On the other hand, each channel keeps associated a producer CHAT for the port producing tokens into the // Mapping description file // Map tasks .MAP –TASK task_1 INTO –PROCESSING PE_1 ; .MAP -TASK task_id INTO -PROCESSING PE_name ; .MAP -TASK task_id -PORT port_id INTO -PROCESSING PE_name -INTF init_id -LOCAL ; … // Map channels .MAP –CHANNEL channel_1 INTO –MMAREA map_1 ; .MAP -CHANNEL channel_id INTO -MEMAREA map_id ; .MAP -CHAT channel_id -PORT port_id INTO -MEMAREA map_id ; … CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 30 channel and a consumer CHAT for every port consuming tokens from the channel. Moreover, once all channel parts are mapped, CASSE automatically fill out all CHATs with information about how to access the token in the CHB as well as the location of the CHATs. This way, a feasible mapping is obtained whenever the producer CHAT and the consumer CHAT are “visible” each to other as well as the CHB is “visible” for both CHATs. Evidently, such a manual mapping process is error-prone and time-consuming, and particularly when these mappings decisions are made during the design of complex SoC. In order to overcome this drawback, Chapter 3 will present an approach that is capable to generate automatically feasible mappings, therefore improving significantly the productivity of the system designers as well as the efficiency of DSE process. Performance analysis. During performance simulations the tool can obtain and record information about the system execution. This information allows the user to analyse and identify architectural bottlenecks and possible system optimizations at different levels. Based on this analysis, further iterations might be carried out allowing the designer to decide whether to further investigate on modifying both the application and the architecture models, or setting a new mapping. CASSE predefined elements are able to monitor and record two different kinds of information: performance metrics (statistics) and transactions [79]. Such tracing support is possible since all predefined elements incorporate built-in monitors that can be individually enabled to automatically gather statistics and record transactions during their execution. However, performance monitoring can have a significant impact on the simulation speed of the architectural models. Thereby, instead of monitoring and recording all possible information regarding the system execution, the tool provides a fine grain controllability of what information to trace and where to trace it. This fine-grain monitoring is controlled via a separate CASSE description file. This trace description file has to be fed to the tool together with the task-graph, architectural and mapping description files. Finally, it is worth to notice that despite of providing plenty of information about performance, traffic load in the system, and metrics about the resource usage efficiency, etc., other important metrics in SoC design such as power consumption and cost/area are not included in the current analysis of CASSE tool yet. Since the development of CASSE tool is behind of the scope of this thesis, this aspect is encouraged to be addressed as future work. CHAPTER 2 31 Refinement. Finally, once the expected requirements are fulfilled with a specific application/architecture/mapping instance, the system is ready for implementation. Hardware modules can be progressively refined from more abstract to more accurate (even synthesizable) descriptions in SystemC, and verified within the architectural model just by replacing predefined elements of the tool libraries with accurate models of external custom components. Likewise, software modules might be directly taken into an embedded compiler, and later integrated again in the system by means of an external component that integrates an ISS. 2.3.2 CASSE tool structure As depicted in Fig 2.7, CASSE is structured in three layers: Fig. 2. 7 CASSE internal structure. Front-end layer. The front-end layer serves as a user interface that controls the tool. As mentioned before, there are four groups of description files that allow the system designers to fully control the creation and configuration of each ESM: the task-graph (or application) files, the architectural file, the mapping file, and the trace file. Back-end layer. This layer implements the core functionality of the tool. Besides a parser that reads and interprets the description files (specified by the designers), this layer contains also two specific libraries: the application library (APP) and the architecture library (ARCH). On the other hand, CASSE is able to carry out two kinds of simulations: functional simulations and performance simulations. While functional simulations only require the task-graph file, CASSE needs to read and parse the task-graph, the Front-end layer Back-end layer Kernel layer Traces & Statistics User Tasks Task graph file Mapping file Architectural file External components Tool libraries APP (TTL) ARCH (PE, NE, SE, ICCP ) Parse r Traces collector Application modeling Mapping Architectural modeling Simulator core Functional simulation Performance simulation CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 38 0 200 400 600 800 200 400 600 800 Mhz MBytes Initial solution Optimized solution 1 Optimized solution 2 Fig. 2. 13 Total synchronization load generated by different mapping solutions. 2.4.2.4 Multi-applications analysis Following our purpose of building a complete CVS, another specific objective of our analysis is to determine the possibility of mapping other applications in this platform and still complying with the real-time tracking system requirements. The typical characteristics of image-processing, audio-processing, and signal-processing applications, for which regular streams of data are processed at a constant rate or periodically, were taken into account to develop these new applications. More specifically, our tracking application was analysed in different scenarios, where it was coexisting with four different types of traffic generated by an additional producer-consumer application in the same system. That is, the producer-consumer application works like a generator of synthetic traffic load in the system, and it can generate four different kinds of traffics. First, constant traffic, where the new application shares the same shared memory with tracking application. Second, periodic traffic was taken into account, where the new application accesses the main memory at a specific rate, in this case with periods of 10 ms and 20 ms. Finally, random traffic also is included in this analysis. This analysis allows the designer to know how the target system performance is with regard to additional load produced by another application in the system. The results of this analysis are shown in Fig. 2.14. In this case, tasks of the new application (i.e., the producer and the consumer) are mapped manually onto PE 3 and PE 5. Moreover, the channels of the new tasks graph were also mapped onto the shared memory. Some experiments were performed varying the data size processed on the new application. Following with the last example, the tracking system performance running at 400 MHz and with a ×10 acceleration and in the presence of the other application is shown in Fig. 2.14. The results indicate that the tracking system can work at 25 frames/s when an additional application produces a CHAPTER 2 39 constant traffic load with data of size lower than 100 Kbytes, or another one which produces traffic load with period of 10 ms, being its data size lower than 2 Mbytes. constant random periodic (10ms) periodic (20ms) 15 20 25 30 1246810 MBytes Frames/s Fig. 2. 14 Tracking system performance with other applications running on the target MPSoC platform. 2.5 Conclusions At the same time that the design abstraction level is raised to system level, an important number of modelling and simulation tools emerged to support system designers to make design decisions and DSE in an early design stage. In our case, a SystemC-based modelling and simulation tool called CASSE, developed at Research Institute of Applied Microelectronics (IUMA) of ULPGC, is used in this thesis. CASSE is based on the YChart principle, and it allows the system designers to specify an application model, architectural model and a mapping model by means of the textual description files. As a result, CASSE generates an ESM that is used for performance simulation. Although a wide range of system metrics (such as performance and system traffic load) can be obtained from CASSE after each simulation, other key design metrics (like power consumption and cost/area) are not provided by the current version of CASSE yet. On the other hand, all the aforementioned models (i.e., task-graph, architectural and mapping) need to be created manually by the system designers prior to each DSE experiment. For instance, the system designers have to change/configure manually such description files each time a new design decision is taken (e.g., different mappings, distinct combinations of component configurations, platform topology, etc). From our point of view, such manual design process is time-consuming, error-prone, and overall, inefficient for exploring large design spaces. Therefore, some kind of new infrastructure is needed to support the system-level DSE. Such infrastructure should (i) include some CASSE: A SYSTEMC-BASED MODELLING AND SIMULATION TOOL 40 mechanisms to generate automatically each ESM, (ii) allow the system designers to select the most appropriate technique to lead the search process, and (ii) be capable to integrate the simulation tools in order to evaluate different alternatives of design space, as well as provide the system metrics to guide the search algorithms. All these challenges will be addressed in Chapter 3 of this thesis, where a new DSE methodology and developments of the NASA framework are explained. Chapter 4 will explain new concepts and strategies developed in this thesis for application mapping and searching in DSE of heterogeneous MPSoCs, using NASA as our prime framework and showing ways to incorporate other frameworks. Chapter 3 Methodology and infrastructure for multidimensional DSE his chapter presents several contributions of this thesis: NASA infrastructure, dimension-oriented DSE methodology, and a generator of architectural platforms. Moreover, we also illustrate how NASA can couple the aforementioned approaches and CASSE in a unified environment, allowing thus the system designers to explore large design spaces in an efficient and automatic way. Finally, we configure NASA with genetic algorithms in order to perform several sets of DSE experiments. The goals of these experiments are to demonstrate the capability of NASA framework and to prove the benefits of our dimensionoriented DSE methodology. T 43 3.1 Introduction 3.1.1 Design space dimension System-level design space exploration (DSE) consists of exploring a wide range of design choices during the early design stages, allowing system designers to have a rapid and complete vision about the impact of different design options on the system performance and behaviour. As a consequence, such early DSE is becoming a key element in system-level design as it influences heavily the success or failure of the final product, and can avoid wasting time and effort in further design steps without the possibility of meeting design requirements because of an inappropriate system design decision. In modern SoC design, a wide variety of system parameters and design choices should be explored in order to find an optimal system design or design point. Such design decisions include the number and type of PEs, SEs and NEs in the MPSoC platform, the architectural topology, the mapping of tasks and communications onto architecture resources, and scheduling policies. This way, the design points are usually the result of specific combinations of choices related to some features of the design. Fig. 3. 1 An example of the classification of design options in design space dimensions. On the other hand, the design decisions can be clustered in dimensions2 of design space, as illustrated in Fig. 3.1. Typically, a dimension could represent design decisions that are 2 It should be noticed that design decisions (or options) clustered in each dimension depend on the system designers, so different designers can use distinct criteria to fix the definition/classification of each design space dimension. Component parameters PE SE NE Topology General organization, relations among components, resources allocation, restriction on number and type of instantiated components Architectural Components Voltage, operating frequency, scheduler, context switch overhead Latency, word size, storage capacity I/O buffered, bandwidth, latency, energy Mapping HW/SW, clustering, migration Resource sharing, cache structure, data transfer size Arbitration policy, communication protocol overhead METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 44 orthogonal to each other. In the example shown in Fig. 3.1, three dimensions can be distinguished: mapping, architectural components, and platform. Here, the platform dimension explores the topology or platform structure, defining the number of architectural elements and their topological interconnection; the architectural components dimension explores design decisions about the types of architectural components (PE types, SE types, etc.) inside a platform architecture; finally, the mapping dimension explores different mappings of application tasks and communications onto the underlying architecture. Evidently, the more details (or dimensions) taken into account, the larger the design space that needs to be searched, and therefore the more costly the analysis. 3.1.2 Generic infrastructure for multidimensional DSE In order to assess such aforementioned large amount of design options (and consequently, large number of system design alternatives), the system designers can use different evaluation techniques: analytical model and/or simulations, as mentioned in Section 1.4.2.2. Although both techniques have received significant research attention during the last decades [58, 91-93], we will focus on simulations-based DSE in this chapter, while DSE based on analytical methods will be addressed widely in Chapter 4. However, taking into account our experimental results shown in Chapter 2, we can see that creating manually each ESM and/or simulating exhaustively all possible design points of the design space is prohibitive for designing modern SoCs. Thus, the simulation tools only provide a partial solution for DSE, since an overall framework is still needed to systematically explore the design space. In fact, as pointed out in Section 1.4.2, the process of system-level DSE logically consists of three interdependent components: search mechanisms, ESM generator, and evaluation methods, such that a DSE framework should not only allow for exploring large design spaces in a time-efficient and automatic way, but also should be flexible and reusable to carry out different DSE experiments. Although many DSE approaches have been proposed, three common factors can be identified in all of them: 1) DSE efforts are usually targeted to specific system-level simulation tools (or analytical evaluation method), where each effort typically uses a different kind of simulator. Consequently, it is hard to re-use these DSE frameworks and the elements available in them. 2) Setting up the DSE experiments can be very labour intensive. It is often the case that for every experiment, control scripts need to be (re-)written to manipulate the simulation CHAPTER 3 45 parameters and configuration files (specifying the design instance to evaluate) according to the algorithm that searches through the design space. These scripts are often inflexible and hard to re-use for different types of DSE experiments, i.e., assessing different parameters or parameter ranges. 3) In spite of the wide variety of eligible architectures for implementing embedded systems applications, many DSE experiments are focused on a particular class of MPSoC architectures only. This mainly happens because no tools are currently available to automatically and generically generate different architecture models from abstract input descriptions and, consequently, designers have to write such models manually. This latter is an error-prone task and one of the bottlenecks in improving designer's productivity, and severely limits the size of the design space that can be explored in a reasonable time. In summary, to the best of our knowledge, there does not exist a generic infrastructure to facilitate and support system-level MPSoC DSE experiments, and to foster the re-use of software in the context of system-level MPSoC DSE. This calls for a unified framework that integrates and couples both simulation and search mechanisms to efficiently and systematically explore design spaces, as well as a fast tool to automatically generate a wide range of architecture models, so that a large variety of architectures can be easily explored and evaluated. In this chapter, we present a new methodology, techniques, and an infrastructure to address the above challenge. On one hand, we introduce a new generic system-level DSE infrastructure implemented in C++, called NASA (Non Ad-hoc Search Algorithm) [94]. Its main goal is to provide a single, common, and modular framework for systemlevel DSE experiments. It allows for incorporating different (existing) system-level simulation tools as well as different combinations of search strategies by means of a simple plug-in mechanism. On the other hand, an architectural platform generator has also been integrated in NASA to free designers from the efforts to manually create architecture models. Thus, this automation improves the design productivity and enables the designer to focus on the more valuable issue of making design decisions. Finally, we propose a new methodology for system-level DSE called dimension-oriented DSE approach, which allows designers to configure the appropriate number of search algorithms to simultaneously co-explore the various design space dimensions. As a consequence, our framework provides a flexible and re-usable environment to METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 46 systematically explore the multidimensional MPSoC design space, starting from a set of relatively simple user specifications. 3.2 Related work Performing DSE in a time-efficient and accurate way is not a new problem and there exists a large body of related work in this area. Most of the approaches in the embedded systems domain are targeted to the system-level exploration of the optimal distribution of application tasks on a selected set of PEs such as generic RISC processors, ASIPs, or dedicated hardware IP blocks considering time constraints, power consumption, and/or hardware area/cost [91, 95-99]. To meet these constraints, numerous mapping approaches can be applied such as genetic algorithms [100, 101], combining analytical models and simulation tools [92, 102], and/or iterative heuristics methods [103]. Although these approaches are fairly efficient to explore various alternatives for mapping a specific application onto a target MP-SoC architecture, they typically still require significant effort to (re-)write scripts that control the evaluation mechanism (analytical model or simulator) during the search throughout the design space. In fact, this often means that there exists a repetitive effort in building customized scripts and/or architecture models for every different kind of DSE experiment. Thus, automating such a process becomes a key element in terms of reusability and flexibility for larger design space explorations in the design of an heterogeneous multiprocessor architecture. Unfortunately, for architecture model generation, only a few approaches have been developed [93, 104, 105], and for most of them, manual interventions are still needed, which is time-consuming and error-prone. Moreover, these useful generators still need to be integrated in a single environment and coupled to some kind of evaluation tool(s) (analytical model or simulator) and search algorithms to completely automate the entire DSE process. Several proposals to integrate external design-point evaluation tools into a DSE environment can also be found in literature. In [46], a hierarchical and three-phase DSE methodology is presented. It facilitates the integration of simulators by using a set of tooldependent interpreters or adapters. Angiolini et al. [106] present a framework that integrates an ASIP tool-chain within a virtual platform to explore a number of axes of the MPSoC configuration space. However, unlike our work, this framework does not allow the CHAPTER 3 47 integration of external search methods. Moreover, it still requires human intervention in the feedback loop of the searching and optimization process. The MultiCube project [102] has similar objectives as the framework presented in this chapter, but it targets the exploration of the configuration space of homogeneous chip multiprocessors rather than system-level MPSoC platform DSE. This implies that it has limited or no capabilities to explore different application-to-architecture mappings, heterogeneous processing elements or different interconnection schemes. Other works have also developed a modular interface-based system-level MPSoC DSE framework [107, 108]. In these cases, different search algorithms can be plugged in, but the resulting DSE is limited in terms of the target MPSoC platforms that can be explored. Consequently, the different architecture instances that can be derived from those fixed MPSoC platforms, may not be flexible enough to meet the requirements of different application domains, and not scalable enough to meet the computational needs of a large variety of applications. Künzli et al. [109] proposed a generic and modular framework based on PISA [110] for DSE of embedded systems. The PISA interface separates the problem-dependent variation and estimation part from the generic search and selection. The resulting two parts are implemented as independent processes that communicate via text files. As a result, it resolves the problem that existing optimisation methods cannot be coupled easily to the problem-specific part of a design exploration tool. But, unlike our work and to the best of our knowledge, they have only coupled analytical models to evaluate design points. This means that, e.g., the problem of incorporating a system model generator and external simulation tools has not been addressed. Using pre-compiled and ready-to-use search algorithms available at [111] of the PISA framework, Madsen et al. [112] have created a multi-objective DSE framework. Different mapping alternatives can be evaluated (by means of analytical models) for a fixed or flexible platform during the exploration process. Moreover, the chosen representation formats for internal interfaces in [112] are problem specific, which means that they should be modified for each particular problem. In our case, these are dynamically and automatically updated according to an input constraints file. Finally, the kind of platforms generated in [112] is limited to hierarchical bus topologies, while our approach is not restricted to analyse a particular architecture. METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 48 3.3 Preliminaries and definitions Before explaining the NASA framework in detail, the terms and notations used along this chapter are briefly presented. Definition 1. A design point is a system design specification defined by a set of specific design options. An example of such a design point would be an architecture consisting of three ARM processors and two memories connected to a single AMBA bus, where the application functionalities are mapped onto a single ARM processor, and the communication channels are assigned to both memories. In this context, a feasible design point is a specific design of the system that meets the user constraints in terms of such design options. This means that, for example, only the available number and types of architectural components (PEs, SEs, NEs, etc.) can be used to create a feasible architecture. Moreover, the functionalities or tasks of an application have to be mapped onto processing resources actually instantiated in the architecture. Further, communications between application tasks must be mapped onto storage resources which are actually accessible by the PEs onto which the communicating tasks are mapped. If at least one of above conditions is not satisfied, then the resulting design is classified as an infeasible one. Definition 2. A design space, D, can be formally defined as: k d...ddD × × × = 21 (3.1) Here, di refers to the design decisions or options in a particular dimension i, and the operator × refers to the Cartesian product. Thus, a design point dp in D can be expressed by linking k available design option values (dmap × darc × dpla) corresponding to each of k design space dimensions, where dmap represents a design decision in the mapping dimension, while darc and dpla express a particular design decision for the architectural component and the platform dimensions, respectively. This way, finding the optimal or near-to optimal design point consists of a multidimensional exploration process, searching for the best combination of values in all dimensions of D that optimizes all the imposed objectives (e.g., performance, power, cost, etc.). Definition 3. The size of a design space is equal to the product of the cardinalities of the set di, ∀i=1..k: CHAPTER 3 55 module implementation. Clearly, this makes our framework more re-usable and extensible. The last important interface in NASA is the architectural intermediate file. It describes the architectural platform design of each design point in a single file and, as will be explained in more detail later, it is gradually constructed using the platform and architectural components strings: the platform string produces a topological template instance of the design point, while the architectural components string specifies the types of the architecture components in this template. The architectural intermediate file is used by the Translator to generate an architecture model of the design point in question. Moreover, it is also used to check the mapping feasibility. Note that platforms are not fixed entities in NASA but are often also part of the exploration. Therefore, the Feasibility Checker requires, e.g., connectivity information specifying which and how PEs are connected, and which SEs are shared by which PEs. This information is needed to detect and repair infeasible mappings, as will be explained in Section 3.5.3. 3.5.2 Search module and dimension-oriented co-exploration This module performs the actual search through the design space, iteratively pinpointing (a set of) design points that need to be evaluated by means of system-level simulation. As mentioned before, NASA applies a dimension-oriented design space exploration approach and currently distinguishes three dimensions (or levels): platform, architectural components and mapping level. This way, each dimension can be co-explored simultaneously using a single search algorithm, or using multiple and possibly different search algorithms for the various dimensions. The designer simply configures the number of search algorithms to be used in the exploration process. In this context, co-exploration means that, in spite of using one search algorithm per dimension, we do not perform the system-level design space exploration as multiple independent explorations, but instead, the results from all dimensions are simultaneously taken into account. It should be noted that, independently of the number of search algorithms used in NASA, the Search module always provides x sets-of-strings (or design-options files) to the Feasibility Checker, where x is equal to the number of dimensions of the explored design space (x=3 for our platform, architectural components and mapping dimensions). For example, when a single search algorithm is used in the Search module, adapter modules will be automatically plugged in to translate the inputs and outputs of the Search module to comply to this x set-of-strings interface, as illustrated in Fig. 3.3b. METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 56 If multiple search algorithms are used to explore the design space, then there are many ways of linking the design decisions of each dimension to form a design point specification. For example, using a pyramidal technique (as shown in Fig. 3.4a), all (or some) of the design decisions in the mapping dimension are linked with each of the decision decisions in the architectural components dimension, while the latter are again all linked with each of the design decisions in the platform dimension. However, this means that the number of design points to be evaluated in each search iteration grows exponentially with the number of design decisions (or strings) of each dimension. The other extreme is a pure one-to-one linking technique (as shown in Fig. 3.4b). This means that each design decision in each dimension is linked to only one design decision in the other dimensions. Thus, the number of design points explored per iteration by the Search module is equal to the number of design decisions (or strings) contained in any design-options file, assuming that all design-options files have the same number of strings. Clearly, this significantly reduces the number of required evaluations because of the linear relationship between the number of design decisions and design points. However, this approach may suffer from a possible convergence problem due to underexploration, i.e., discarding a design decision (e.g., a specific platform instance) too soon based on the results of a premature evaluation. Example 3.1. Let }d,d,d{A A map A arc A pla =be a design point built with platform A pla d, architectural components A arc d and mapping A map d, while }d,d,d{B B map B arc B pla = is another design point formed by platform B pla d, architectural components B arc d and mapping B map d. If it turns out after a single simulation that the fitness value of A is better than that of B, then this does not mean that platform A pla dor architectural components A arc d are always a better choice than B pla d and B arc d, but we can affirm indeed that the combination of design options }d,d,d{A A map A arc A pla = is better than }d,d,d{B B map B arc B pla =. For instance, this latter does not guarantee that }d,d,d{ A map A arc A pla can provide a better fitness value than }d,d,d{ C map B arc B pla , where C map d is another feasible mapping for B. To address this under-exploration problem, we use a variant of one-to-one linking of design decisions. In this technique, unlike the pure one-to-one technique, only design decisions from the dimension of the lowest abstraction level (i.e., the mapping dimension in our case) are evaluated and updated during each search iteration. The search CHAPTER 3 57 algorithms for the higher-level dimensions (i.e., the platform and architectural components dimensions) keep collecting the fitness values (for different mappings) without actually changing their design decisions during a specified number of iterations, referred to as the collecting iterations (δ). Only when the search has reached δ iterations, design decisions are updated, after which the process starts again. Obviously, the higher the abstraction level, the more design alternatives can be derived for a single design option (e.g., a multitude of architecture instances can be obtained from a single platform) and, consequently, the higher the value of δ should be. Note that the above mentioned feedback information, i.e., the fitness values, needed to guide this search through the design space, are iteratively provided by the Evaluator module, which will be explained in Section 3.5.7. a. Piramidal linking technique. b. One-to-one linking technique. Fig. 3. 4 Different techniques to link design decisions in a single design point. 3.5.3 Feasibility checker The main task of the Feasibility Checker is to detect infeasible design points and repair those design points if possible. During this checking process, all sets-of-strings (or design-options files) are checked in a hierarchical fashion. For example, for our 3-level exploration as shown in Fig. 3.3a, in order to distribute or map the functionalities of the application onto different architectural components, a feasible architectural platform is Platform dimension A rchitectural components dimension Mapping dimension …… d p la1d p la j d p lak …… darc j -1 darc j darc j +1 …… dma p j -1 dma p j dma p j +1 Design point Design decision string …… d p la1d p la j d p lak …… darc1darc j dar c k …… dma p 1dma p j dma p k Design point (dpk) Platform dimension A rchitectural components dimension Mapping dimension METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 58 first required to be able to reflect that decision. Thus, the platform string is first checked to determine whether or not the specified platform template contains a valid topology and, e.g., whether it does not contain isolated islands of components (to be discussed in more detail in the Example 3.2). Next, the architectural components string is checked to determine whether or not the number and types of selected architectural components in the platform template comply with the constraints provided by the user. For example, if a design point deploys 4 ARM processors while the user has specified that only 2 ARM processors can be instantiated, then we have an infeasible design point. Finally, the mapping string is checked for infeasibility, e.g., when application tasks are mapped onto PEs that have not been allocated in the platform, or in the case there is no shared memory to map a logical communication channel between two tasks that have been assigned to different PEs. So, each design point is globally checked, i.e., taking all dimensions of the design point into account. If an infeasible design point is detected, then different kinds of repair mechanisms can be applied, depending on the dimension where the problem occurs. Note that different repair techniques can also produce different feasible solutions from the same infeasible design decision. In our current implementation, we use heuristic minimum-distance repair techniques, which introduce a minimum number of modifications to an infeasible design string in order to obtain a feasible one. As a consequence, our repair techniques only have a minimal effect on the run-time of the framework. In the aforementioned infeasible mapping example (i.e., no reachable memory for two communicating tasks), only the communication channel of those two application tasks should be relocated into an reachable memory if a feasible mapping can be derived from such a repair3. The impact of these repair mechanisms on the number of explored feasible design points will be discussed in Section 3.6.2. Specifically, our experimental results reveal that these repair techniques can warrant the repair of a high percentage of infeasible design points in the DSE experiments. Apart from separating the Feasibility Checker in three parts (platform checking, architectural components checking and mapping checking), specific sub-modules can also be distinguished inside each part. For example, there is a sub-module for checking the connectivity properties of PEs, one for checking SEs, one that specializes in task 3 Although it is also possible to repair by mapping one of those two application tasks onto another available PE (or even both application tasks onto the same PE), this would require the resulting mapping to re-enter for a new mapping feasibility check as it may cause additional infeasibilities for other communication channels. In the worst case, this may even cause an infinite loop. CHAPTER 3 59 mapping checking, and so on. Since all these checking sub-modules are based on heuristics, the user can freely replace them by other implementations, which again illustrates the flexibility aspect of our framework, as mentioned in previous sections. 3.5.4 Architectural platform generator The main mission of this module is to provide the architectural description for each design point by means of combining both feasible platform and architectural components information, which are contained in the strings of their respective design-option files. The resulting architectural description file is used later for (i) feasibility checking of mapping strings, and (ii) as input (to the Translator) to generate the architectural model. Thus, the Architectural Platform Generator can be considered as the first stage of the ESM generation process. Basic Topology Unit An architectural description is created in two steps: platform or topological template generation and architecture instance generation. The basic building block of these descriptions is the so-called Basic Topology Unit (BTU). As shown in Fig. 3.5, the BTU is a logical pattern consisting of a network container (the gray component) and a variable number of element containers (the white blocks). These element containers are labelled inside each BTU and can, in a later stage, be instantiated as architectural components such as PEs and SEs. The number of element containers in a BTU depends on the user specifications, like the maximum number of PEs and SEs in a platform. Note that network containers cannot directly connect to each other, while element containers can connect to both element and network containers. Fig. 3. 5 Example of a BTU generation and element container. Meta-platform The BTU is labelled and replicated a number of times to form a meta-platform, which is used later in topological template generation. In principle, the meta-platform is used as a BTU 12345 Network container max. PE=3 max. SE=2 max. NE=3 PE={ARM, MIPS} SE={SDR, DDR} NE={BUS, BAR} Connectivity=2D … User s p ecifications 1 2 3 4 5 6 7 Element container Element containers=5 Network containers=3 Connectivity=2D … METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 60 basis from which all feasible platform instance descriptions can be (gradually) derived and generated. The number of BTU replications in the meta-platform depends on the maximum number of NEs and connections allowed among element containers, as specified by the user. The latter is referred to as connectivity, which defines for each element container both the available links and the directions (represented with numbered arrows in box of element container of Fig. 3.5). Thus, a BTU can be replicated through two or three directions and, as consequence, different kind of meta-platforms can be generated according to the user specifications. A 2D meta-platform generation process is shown in Fig. 3.6, although a 3D meta-platform can be also generated if the gray links of an element container (see Fig. 3.5) are also used during this process. It should be noticed that the generation of the BTUs as well as the meta-platform is performed statically (but automatically) before the actual DSE process. Fig. 3. 6 Example of 2D and 3D meta-platform generation. Platform template generation Driven by the exploration at platform level (in Search module), the meta-platform is used to generate topological template instances (as depicted in Fig. 3.7). To this end, the set of strings of feasible platforms is used to instantiate the topological templates from such a meta-platform: each string sets (for one design point) the type(s) and number of NEs in the platform. Moreover, the number of element containers in the platform as well as their BTU 1 1 2 3 4 5 BTU 2 1 2 3 4 5 BTU 3 1 2 3 4 5 BTU 4 1 2 3 4 5 BTU 5 1 2 3 4 5 BTU 6 1 2 3 4 5 2D Metap latform Network 1 Network 2 Network 4 Network 3 Network 5 Network 6 Meta-platform generation BTU 1 2 3 4 5 Network container Element containers=5 Network containers=3 Connectivity=2D … 3D Metap latform BTU BTU x 1 2 3 4 5 Network x CHAPTER 3 61 connectivity properties are also determined. Finally, a type classification of the element containers is made. This latter means that for each allocated element container in the BTUs, it is indicated whether it contains a PE or a SE. Note that, as explained in Sections 3.5.2 and 3.5.3, these platforms have been selected by the Search module and checked by Feasibility Checker. The latter repairs strings describing any infeasible topological templates such as, for example, isolated BTUs that do not connect to any other BTU, architectural elements with incorrect connectivity links, and other inconsistencies. Fig. 3. 7 Platform instance generation and platform string checking. Example 3.2. During the platform exploration process, the search algorithm could assess infeasible platform strings with isolate BTUs, as shown in Fig. 3.7. In this context, isolate BTU means that a BTU is not connected/linked to other BTUs, and as a result, an incoherent topological template is generated. When these cases are detected by the Feasibility Checker Module, our minimum-distance repair algorithm tries to correct them if possible. In the example shown in Fig. 3.7, both either BTU 4 or BTU 1 can be reallocated in BTU 2 in order to generate a feasible platform template. Architecture instance generation Finally, in order to obtain the complete specification of the architecture platform for each design point, the topological templates are further refined. In this process, which is driven Feasible p latform Platform generation Platform strings SEARCH + Meta-Platform Platform exploration Feasible platform strings FEASIBILITY CHECKER + Metap latform Architectural components … NE1 NE2 NE3 NE4 NE5 NE6 1 0 0 2 0 0 Each string value indicates the NE type in the Btu Users specification NE type1 = Bus NE type 2 = XBA … BTU 1 1 2 3 4 5 BTU 2 BTU 3 BTU 4 1 2 3 4 5 BTU 5 BTU 6 Infeasible platform (isolate BTU) bus xba Architectural components … NE1 NE2 NE3 NE4 NE5 NE6 1 2 0 0 0 0 BTU 1 1 2 3 4 5 BTU 3 BTU 4 BTU 5 BTU 6 bus BTU 2 1 2 3 4 5 xba Platform strin g s Platform strin g s … … Examples of topological template instances XBAR SE PEPE PE BUS PE SE BUS PE PE SE … … … METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 62 by the exploration at architecture component level, the same topological template can be reused to derive different architecture templates. For this propose, the actual component types of the element containers in a template are added. In the example of Fig. 3.8, this means that, e.g., a PE allocated in an element container either becomes an ARM or MIPS processor, and the SEs either SDRAM or DDRAM. Evidently, all this information is also provided by the strings of feasible architectural components. Fig. 3. 8 Example of architecture instance generation process. 3.5.5 Translator As mentioned before, in order to evaluate selected design points using a system-level simulator that is plugged into the framework, an ESM for each design alternative should be generated first. Such an ESM, composed of an architecture model, an application model and a mapping model, can be provided by the Translator module in an automatic way. To this end, it uses as input the architectural intermediate file (output of the Architectural Platform Generator), the application specifications and the strings that describe feasible mappings, respectively. Thus, the Translator can be considered as the second (and last) stage in the generation process of the simulatable system model. There exist three relevant benefits in including this module in our framework. First, the Translator converts NASA’s internal format of a design point to a file-based format that is specific for the target system-level simulator. Note that in order to integrate a systemlevel simulator in NASA, it is required that the simulator allows for explicitly describing the design points that need to be simulated using some kind of file format. Second, the resulting ESM should be simulator-specific, i.e., only allowed syntaxes and command lines (for each simulation tool) have to be used. Fig. 3.9 illustrates the conversion to Topological template XBAR SE PE PE PE BUS PE SE BUS PE PE SE … A rchitecture instances XBAR DDR … ARM MIPSARM BUS BUS DDR ARM ARM MIPS DDR SEARCH + FEASIBILITY CHECKER Architecture generation Feasible architectural components strings Architecture exploration CHAPTER 3 63 different architectural models (from a single internal specification) for two system-level simulation tools, CASSE [91] and Sesame [58]. Both tools can be integrated in NASA since they comply with the condition of using a file-based format. However, a particular design point is described in different ways in both simulators: CASSE uses command-line expressions, while Sesame is based on an XML-based format called YML (Y-Chart Modelling Language). Finally, last but not least, the Translator module constitutes itself as an interface (or layer) which separates simulators-dependent and simulators-independent modules, as shown in Fig. 3.2. This implies that the integration of a new system-level simulator in NASA only requires the adaptation of the Translator module, i.e., tailoring the Translator for each different simulator, while all other modules remain unaffected. This adapter function of the Translator again highlights the flexibility and re-usability aspect of our framework. Fig. 3. 9 Plug-in examples for generating architectural model in Sesame and CASSE. 3.5.6 Simulator At this moment, we have integrated CASSE in NASA, and another system-level simulator called Sesame is in the process of being integrated. Both tools follow a Y-Chart methodology, covering application and architecture modelling, as well as mapping and analysis within a unified simulation environment. Since the implementation of CASE tool has been widely discussed in previous chapters in this thesis, the interested readers are referred to Chapter 2 for more detailed information about CASSE. <network name=“BUS" class="net"> <port name="in0" dir="in"></port> <port name="out0" dir="out"></port> <node name=“MEM" ... <property name="class" value="buffer_memory"></property> <port name="in0" dir="in"></port> ... <node name=“PRO" ... <property name="class" value="processor"></property> <port name="out0" dir="out"></port> ... <link innode=“BUS" inport="out0" outnode=“MEM" outport="in0"> <link innode=“PRO" inport="out0" outnode=“BUS" outport="in0"> YML-basad architecture model .create –network BUS –n_input 1 –n_output 1 ; .configure –network BUS input 0 –rqfifo 1 … .configure –network BUS output 0 –rqfifo 1 … .create –storage MEM –n_target 1 ; .configure –storage MEM –size 256 ; .configure –storage MEM –target 0 –width 32 … ... .create –processing PRO –n_init 1 ; .configure –processing PRO –init 0 –width 32 … ... .bind –link LINK1 to –network BUS –input 0 ; .bind –link LINK1 to –processing PRO –init 0 ; .bind –link LINK2 to –network BUS –output 0 ; .bind –link LINK2 to –storage MEM –target 0 ; … Command lines based architecture model Architectural intermediate file Sesame Translator CASSE Translator Translator module METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 64 3.5.7 Evaluator During simulations, quantitative information about the system execution (e.g., data about performance, cost/area, and power consumption) can be gathered and dumped into files for later inspection. All these metrics can be used in system-level DSE to find a set of Pareto optimal design points, which then yields a multi-objective optimization problem. The essence of the Evaluator module is to provide this feedback about the quality of a set of evaluated design points to the Search module, influencing the search decisions taken in the exploration process. Separating the Evaluator from the Search module again provides flexibility and enhanced reusability of the components in NASA. It allows for easily changing the optimization objectives or the function that quantifies the quality of a design point – using the various metrics such as performance, power and cost – without affecting the other components. Such a function is typically referred to as the fitness function. The Evaluator also provides the flexibility to, e.g., use a single fitness function for all search algorithms in the Search component (performing exploration at platform, architectural components and mapping levels), or to deploy a different, and possibly tailored, fitness function per search algorithm. However, when multiple search algorithms and fitness functions are used together, these should be defined in a coherent way with respect to each other in order to avoid conflicting fitness functions and safeguard convergence. This is because there exists a tight connection between the different search algorithms and their respective fitness functions. This connection should be made explicit. In our current implementation, these relations can be defined by a set of hierarchical fitness functions, which can be used with a variant of the one-to-one linking technique (already explained in Section 3.5.2) to address the under-exploration problem in hierarchical design space explorations with multiple search algorithms. Formally, these hierarchical fitness functions are formulated as follows: ;wzand..w,z; ;LjandI,...,,,i;y)x,...,x,x(fy ;I..i);x,...,x,x(fy wz q jjLkjj kLL j qi i ⊃=∀> ≠∀=∀== =∀= ∑ = βδδ δδ δ 1 21 1 1 21 21 where i L yis the fitness value of a design point of the lowest-level dimension (the mapping dimension in our case) in the search iteration i, I is the total number of search iterations, CHAPTER 3 71 Feasibility Checker module and converted to feasible ones), and the white part indicates the infeasible design points that cannot be repaired by our heuristic minimum-distance repair techniques. 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 1 2 3 4 5 6 7 8 9 1011121314151617181920 Iterations Infeasibles Repaired Feasibles a. 1GA: average percentage of repair: 84.21%. 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 1 2 3 4 5 6 7 8 9 1011121314151617181920 Iterations Infeasibles Repaired Feasibles b. 3GA: average percentage of repair: 86.68%. Fig. 3. 11 Average percentage of feasible, repaired and infeasible design points per iteration in our DSE experiments. From these data, it can be seen that our repair techniques can repair more than 84% of detected infeasible design points in each iteration, and as a result, more than 91% of explored design points can be actually evaluated by the CASSE tool. Thus, it seems that the repair mechanisms significantly affect and improve the efficiency of the DSE experiments. 3.6.2.3 Convergence rate and number of iterations The convergence is illustrated in Fig. 3.12, where the horizontal axis indicates the number of explored design points (and iterations) and the vertical axis represents the fitness values in terms of processed data packets/s. Fitness values come from the used simulator, which is in this case the CASSE tool. Investigating these data, it can be seen METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 72 that 1 GA-based experiments have a higher convergence rate (i.e., a steeper slope) than 3 GA-based experiments in the first iterations. This phenomenon is the implicit effect of using the hierarchical fitness functions (explained in Section 3.5.7) and the variant of the one-to-one individual linking technique (presented in Section 3.5.2) in 3 GA-based experiments. Fig. 3. 12 Average fitness values per iterations. However, when the number of iterations increases, 3 GA-based experiments do not only gradually and progressively reach higher fitness values than 1 GA-based experiments, but they can also ensure that most of the individuals in each iteration satisfy the real-time restriction (1250 packets/s). In the 1 GA-based experiments, on the other hand, mostly design solutions with fitness values lower than the real-time restriction are reached. Moreover, the 1 GA-based experiment hardly improves or provides better design alternatives with the evolution of iterations. The latter could indicate that the GA is trapped in a local optimum, which occurs when design points explored in each experiment are not sufficiently different or well-distributed (i.e., partial coverage) to properly capture the design space in its entirety (e.g., covering only partially or some regions of the design space), caused by an insufficient variety of new individuals introduced in each iteration (i.e., a low incremental diversity) that prevents the populations to escape from such local optima. These aspects can be demonstrated in both Fig. 3.13 and Fig. 3.14. 3.6.2.4 Diversity and search approach Each curve in Fig. 3.13 represents the percentage of new and different design points introduced in each iteration that have not been explored in any of previous iterations, i.e., the incremental diversity per iteration. These results highlight that 3 GA-based experiments clearly yield a higher incremental diversity per iteration than 1 GA-based 400 600 800 1000 1200 1400 0 100 200 300 400 Explored design points Fitness values (packets/s) 0 5 10 15 20 25 30 35 40 Iterations 1GA1x6 1GA2x1 3GA1x6 3GA2x6 Real time CHAPTER 3 73 experiments, and especially in the case of 1 GA with simultaneous mutation (M=1). A direct consequence of the latter result thus explains the resulting gap of the accumulated diversity between both approaches, as already shown in Fig. 3.10. Fig. 3. 13 Incremental diversity per iterations. 3.6.2.5 Convergence, design points concentrations and local optima All design points explored by each of the selected group of experiments (corresponding to the four mentioned NASA configurations) are separately shown in Fig. 3.14, where each axis represents one design space dimension in our 3D design space, i.e., mapping, architectural components and platforms. Moreover, for a fair comparison, each axis in Fig. 3.14 contains all ordered design-decision instance numbers (i.e., the canonical representations of the strings for the platform, architectural components and mappings dimensions) explored together by these four groups of experiments. It can also be seen in Fig. 3.14 that the design points explored in the 3 GA-based experiments are scattered over almost the whole design space (high coverage) and are characterized by a high accumulated diversity. The design solutions reached by the 1 GA-based experiments, on the other hand, have a lower accumulated diversity and are often concentrated in a single region of the explored design space (lower coverage). This indicates that the searching process is converging toward an optimum, and in this last case, toward a local optimum as already shown in Fig. 3.12. At this point, we also would like to mention that although the size of the design space (approximately 1012 alternatives, as mentioned in Section 3) is much bigger than the number of individuals actually evaluated (maximum 410) in these experiments, the results in Fig. 3.12 and Fig. 3.14 clearly indicate that GA-based DSE in our experiments converge to (local or global) optima after only a relatively small number of iterations. 0% 20% 40% 60% 80% 100% 0 5 10 15 20 25 30 35 40 Iterations Percent of incremental diversity 3GA1x6 3GA2x6 1GA2x1 1GA1x6 METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 74 b. 1GA2x1 d. 3GA2x6 a. 1GA1x6 c. 3GA1x6 Fig. 3. 14 Explored design points by each selected NASA configuration. CHAPTER 3 75 3.6.2.6 The need for refinement It should be noted that design points concentration – a visual indicator of the convergence process – can also be observed in the 3 GA-based experiments. But, unlike the 1 GA-based experiments, the convergence is toward a global optimum or toward a few optimal points. The existence of several optimal points can be illustrated for two NASA configurations based on multiple GAs shown in Fig. 3.14, where more than one design points concentration (or convergence) area can be identified. This is correct since different alternatives can often satisfy a given set of user restrictions. To illustrate the above, two design points (A and B) have been marked in Fig. 3.14d, and their respective architectures and mappings are shown in Fig. 3.15. Fig. 3. 15 Examples of design points found by DSE with pc=0.8, pm=0.3 after 40 iterations. In this case, although both solutions (corresponding to each of the design points convergence regions) have similar performance (A achieving 1371 packets/sec and B 1355 packets/sec), their underlying platform architectures are however quite different. Moreover, they are also over-dimensioned in the sense that not all resources are actually used by the application. Therefore, in this case, designers can perform an additional optimization process in terms of architectural components and/or in terms of mapping. Such refined optimization can be performed in a next and more detailed phase of exploration experiments where, e.g., the platform is fixed and only the architectural components and mapping dimensions are explored more rigorously. Alternatively, additional objectives or fitness functions (such as the cost of designs) can also be taken into account in the optimization process. In the next section, we will further investigate refinement by fixing one dimension (platforms) and then conducting DSE in just a two dimensional space (architecture components and mapping). a. Design point A: 1371 packets/s. b. Design point B: 1355 packets/s. PPC MIPS PPC PPC MIPS PPC SDR SDR DDR BUS Task 3 Task 2,7 Channel 2 Channel 4,9 Task 4 Channel 7,12 Channel 1,8 Channel 6,11 Channel 3 Channel 5,10 Task 1,5,6 PPC MIPS ARM PPC PPC MIPS SDR DDR BUS 1 DDR BUS 2 Task 1,5,6 Channel 2,6-9,12 Task 2 Task 3 Task 4 Task 7 Channel 1,3 Channel 4 Channel 5,10,11 METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 76 3.6.3 Hierarchical refinement and analysis of 2D-DSE with NASA Our second set of experiments presented in this chapter aims at demonstrating NASA’s flexibility and capacity to perform the aforementioned refinement process. To this end, this set of experiments is focused on 2D design space explorations, where design decisions about mapping and architectural components are explored for a particular platform template, i.e., the platform dimension is fixed and no search algorithm is used in this dimension. Obviously, in order to model a specific platform template, designers should properly configure the platform string values for the number and types of element containers in each instantiated BTU as well as their connections with each other. Table 3. 2 Search module and target architecture parameter settings. 3.6.3.1 Fixed platform, variable architectural components and mapping The selected target platform template and available type values for PE and SE are depicted in Fig. 3.16 and Table 3.2. This platform template can provide architecture models based on two AMBA buses connecting up to six PEs and three SEs. The execution time of the visual tracking application’s tasks has been estimated using ADS, while we assume that the hardware dedicated block (which executes block matching operations of the target application) has a x10 speedup factor with respect to the SW implementation. Note that in this case study, plenty of platforms could have been analyzed in our refinement experiment. However, we believe that we selected a realistic MP-SoC platform template, consisting of several homogeneous processors completed Selection (S) Proportional with etilism Crossover (C) 1-point, pc = 0.5 GA Mutation (M) Independent (M=6), pm = 0.5 Selection (S) Tournament without etilism Crossover (C) 2-point, pc = 0.8 ga Mutation (M) Simultaneous (M=1), pm= 0.3 Collecting iterations (δarc) 2 architectural components dimension Search iterations (I) 21 - Population size (N) 10 Nr. of individuals per iteration PE ≤ 6 ARM and hardware dedicated block SE ≤ 3 DDR and SDR CHAPTER 3 77 with a few coprocessors or hardware dedicated blocks in a bus-based architecture, rather than an MP-SoC based on various PE and NE types having different computational and communication characteristics. Fig. 3. 16 Target platform template for the second set of experiments. 3.6.3.2 2D NASA configuration for DSE Three NASA configurations have been selected in this second set of experiments: 1GA+1Random, 1GA+1ga and 1GA+1GA. The used parameter settings of the genetic algorithms are illustrated in Table 3.2. For example, 1GA+1GA (or 1GA+1ga) refers to two identical (or different) genetic algorithms are used in the architectural components and mapping dimensions, respectively. On the other hand, in the cases of 1GA+1Random, a GA explores different architecture instances by varying the type of SEs as well as the location of the hardware dedicated block in different PE containers of the platform template (since the rest of PE share the same processor type), while a random search algorithm explores different functionality distributions onto system resources in a random fashion. It should be noted that although not included in this set of experiments, an extensive number of combinations of different search algorithms as well as GA parameters could have been used (as already shown in Fig. 3.10 for our first set of experiments). Therefore, the three selected configurations only represent a few samples of NASA’s capacity and flexibility. 3.6.3.3 Results and discussion The results of the above three configurations are shown in Fig. 3.17. The curves show for each of the configurations (i.e., 1GA+1GA, 1GA+1ga and 1GA+1Random) the average fitness values (obtained with twenty different sets of initial populations) reached by all individuals in each of the twenty iterations. From these results, it can be seen that 1GA+1Random can only sporadically reach a few design points that satisfy the real-time constraints. Moreover, it clearly cannot ensure convergence toward any global optimum. On the other hand, although both experiments based on two genetic algorithms can provide solutions that satisfy the input constraints, 1GA+1ga only needs to simulate an average number of 40 individuals before reaching the first individual that satisfies the PE1 PE2 PE3 PE4 SE1 BUS 1 BUS 2 PE5 PE6 SE2 SE3 METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 78 real-time constraint, while 1GA+1GA need to simulate an average number of 60 individuals. This may suggest that more efficient GA-based DSE experiments can be achieved by selecting and configuring appropriately GA parameters. Fig. 3. 17 Comparative results obtained in the second set of DSE experiments. Finally, we would like to highlight another important benefit of our framework. NASA provides not only information about the best solutions but also about all other explored design points in each experiment. This is a key element for better understanding the studied design space, i.e., the more design points are provided to the designer, the more information can be extracted from the explored design space, and therefore, it will allow designers to more easily compare the architectural characteristics of the evaluated design points. That is, it can be very useful for a designer to distinguish the architectural similarities of the design alternatives featuring good fitness values. This last aspect can be illustrated in Fig. 3.18, which shows an example of typical NASA output after each DSE experiment. The set of simulated design points, corresponding to a 1GA+1ga experiment in this case, can form a surface that approximates the landscape of the explored design space. A 2D view of the resulting surface is shown for this experiment since it is based on 2D exploration, i.e., the x axes and y axes of the 2D view contain the explored instance numbers of the mapping and architectural components dimensions, having fixed the platform as mentioned. So, for example, 120 different mappings have been explored in this example. Note that the fitness value associated to each design point is color coded, ranging from red (high fitness value) to blue (low fitness value). Therefore, even when exploring a relatively small number of design points, the distribution of design points in the surface can clearly indicate the location of convergence region(s), while dark red areas can provide a good insight of where the 0 250 500 750 1000 1250 1500 0 40 80 120 160 200 Explored design points Fitness value (packets/s) 0 2 4 6 8 101214161820 Iterations 1GA+1Random 1GA+1GA 1GA+1ga CHAPTER 3 79 sweet spots (design points with higher fitness values) in the design space are located. Moreover, designers can select any design point of the surface, and examine information about that design point such as the parameter values for the mapping and/or architectural components dimensions. Finally, it should be stressed that all these experiments presented in this chapter have been performed in a fully automatic fashion, only providing parameter settings and constraints such as those shown in Table 3.1 and Table 3.2. Fig. 3. 18 Example of NASA output. 3.7 Conclusions In this chapter, we addressed the lack of a generic, flexible, and re-usable infrastructure to facilitate and support system-level MPSoC design space exploration (DSE) experiments. To this end, we have presented a system-level MPSoC DSE support infrastructure, called NASA. This highly modular framework uses well-defined interfaces to easily integrate different system-level simulation tools as well as different combinations of search strategies in a simple plug-and-play fashion. Moreover, we also described a new methodology aiming at multidimensional DSE, dimension-oriented DSE approach, which allows designers to configure the appropriate number of, possibly different and tailored, search algorithms to simultaneously co-explore the various design space dimensions. The result of both contributions is a flexible and re-usable framework/methodology for the systematic exploration of the multidimensional MP-SoC design space, starting from just a set of relatively simple user specifications. In order to demonstrate distinct aspects of our approaches, we have presented a number of DSE experiments in this chapter. First, we compared NASA configurations using a METHODOLOGY AND INFRASTRUCTURE FOR MULTIDIMENSIONAL DSE 80 single search algorithm for all design space dimensions to configurations using a separate search algorithm per dimension. Here, we focused on search algorithms that are based on genetic algorithms (GAs). The experiments have shown that, compared to the more traditional approach of using a single search algorithm for all dimensions, the multidimensional co-exploration seems to be able to find better design points and ensure the convergence toward global optima. Furthermore, the multidimensional co-exploration has a higher diversity and coverage of design alternatives, producing higher quality DSE results. Finally, we have also illustrated NASA’s capability and flexibility to integrate different kinds of search algorithms in DSE experiments. However, in spite of the results presented in this chapter, there are still three aspects that must be proven for our proposed framework/methodology. First, we should have to demonstrate the capability of NASA to integrate other kinds of search algorithms. Second, additional deployment case studies should be carried out to illustrate that our approaches can also conduct multi-objective optimization problems. Finally, since the high total run-time is still being the main drawback of the DSE based on simulations, other exploration strategy alternative should be provided in order to improve the DSE efficiency (in term of total run-time) without losing accuracy in the evaluation. All these challenges will be addressed in the next chapter. STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 88 methodology. Our approach is composed of two independent phases (analytical estimation and system simulation) communicating via a file-base interface, such that the resulting methodology is capable of combining the benefits of both analytical models and simulation tools (i.e., speed and accuracy). In the first phase, a large design space is pruned. To this end, we have developed a set of analytical methods, which considers both deterministic and dynamic system behaviours, to rapidly explore and evaluate design points (in terms of multiple design objectives), as well as to eliminate those design points that cannot satisfy the user requirements. The output of this pruning process is a reduced number of mapping alternatives, which are evaluated accurately in the second phase by a system-level simulation tool in order to find the optimal mapping solution. The overview and implementation details of our hierarchical DSE methodology will be discussed in Section 4.4 and Section 4.5, respectively. Finally, in order to demonstrate the benefits of our hierarchical DSE methodology, we have plugged the proposed analytical methods into NASA framework, performing thus several experiments following our hierarchical DSE methodology. The obtained experimental results will be illustrated and discussed in Section 4.6. This latter will allow us to validate and prove the flexibility and capacity of NASA framework to integrate different kind of search techniques, as well as to address and solve the multi-objective optimization problem, as claimed in Chapter 3. 4.2 Related work In the literature, there exist numerous efforts on DSE aiming to address the problem of the application mapping on MPSoC [94, 99, 103, 107, 109, 116, 117]. In [103], a twophase approach was proposed for the mapping of a real-time application on a homogenous multiprocessor architecture. Basically, they use a set of heuristic-based algorithms to explore distinct alternatives about both task binding and assignment on the architectural components, while an analytical estimation model was applied for the performance evaluation. Kim et al. [98] also proposed a framework based entirely on analytical methods for the DSE. In this case, they focused on the exploration of a design space associated to the HW/SW partitioning decision, as well as the choice of an appropriate scheduling policy for each PE in order to ensure that the application timing requirements are met. Unlike our approach, data dependencies and communication CHAPTER 4 89 overhead are ignored in [98], since they assume an ideal buffering, i.e., the number of messages that can simultaneously circulate on the system is not bounded. And in the case of [103], a simplified communication architecture model at the high level of abstraction is used to estimate the system traffic cost, assuming that a PE can send and receive any number of tokens concurrently, while the communication delay is simply proportional to the amount of communication data and user specified latency parameters for each component. From our point of view, their assumptions are not realistic enough for modelling modern embedded system, and more advanced models are required. In order to overcome this lack of realism on the modelling of communication operations, analytical approaches considering the dynamic behaviour or resources sharing problem have been proposed [107] [115]. Basically, they propose an analytical model for each kind of architectural components that can be later composed to capture and analyze the complete system. However these authors also claim that, in spite that their models can achieve a good level of accuracy (with a reasonable estimation error), it is not easy to combine such models for large systems evaluation yet. On the other hand, system-level simulation tool represents a natural alternative for a more accurate performance evaluation, and/or the analysis of more complex design problems in larger systems. In [116], Sesame [58] was coupled with genetic algorithms (provided by PISA framework [109] [111]) to address the mapping of multiple applications (with different timing requirements) executing concurrently on the same MPSoC. While in [99], CASSE was used in the DSE experiments aiming to find out the optimal mapping of a target application on a MPSoC that works with multiple clock domains. Lahiri et al. [35] also combined PTOLEMY [62, 118] with an iterative algorithm to determine the welloptimized configuration of arbitration schemes for the different NEs on the architecture, such that the system performance is maximized. However, in spite of achieving the desired solutions with a relatively low number of simulations, a high total run time (i.e., in order of hours) of each DSE experiment is still being the common denominator in their works. Finally, and to the best of our knowledge, only a few approaches combining both analytical estimation model and simulation in a single framework have been proposed. One of them is the hierarchical DSE methodology in [46], which has a similar objective as the approach presented in this chapter. Their approach initially uses symbolic constraint satisfaction method to rapidly explore and prune a large design space. Subsequently, the remaining set of alternatives is individually evaluated using trace-driven simulations and STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 90 incorporating more design details (e.g., processor idle time, reconfiguration overheads, energy dissipation, available parallelism, etc). And then, detailed simulations are performed using low-level simulators to select the appropriate design solution. Unlike our methodology, the impact of the resources placement in the architecture, as well as the contention effects on the shared communication architecture are not explicitly explored. Lee et al. [92] present a framework that determines the MPSoCs for the optimal mapping of a given real-time application, i.e., satisfying the real-time constraint while the system cost is minimized. This two-phase approach selects first an optimal set of PEs for the mapping of the target application. Then, by means of a static estimation method based on the queuing model, they explore and prune the design space of communication architectures. And finally, their framework provides a set of interfaces that facilitate the integration of different simulation tools, which can be used to accurately evaluate each solution in the reduced design space, and determine thus the Pareto-optimal set of design points achieving the user constraints. Unlike our approach, they address the DSE as a high-level synthesis problem. Moreover, their queuing model is limited to bus-based topology, while our analytical estimation model is not restricted to a particular architecture, but it is flexible enough to analyze different kind of communication architectures. 4.3 Preliminaries and problem statement In this section, we define the concepts and key assumptions underlying our approach, and follow-up with a formal problem statement. Definition 1. Application model. A real-time application is modelled as a task graph TG={T, L, D}, where T={t1, t2, …, tk} is a set of k periodic tasks that must be executed in a certain order to produce the desired results under a real-time constraint RTC (expressed in seconds), L={l12, l13, … ljk} represents a set of h unidirectional channels or links that communicate the tasks with each other as well as indicate their data dependencies, and D={d12, d13, … djk} specifies the amount of shared data associated to each link. Finally, a task without any input link is called root. Assumption 1. We assume that the application partitioning is done at the functional block granularity, i.e., the basic unit for partitioning (or each task) is a function. Although a CHAPTER 4 91 finer partitioning could be done to exploit parallelism at algorithmic level, this latter is not addressed in this thesis, as pointed out in Chapter 2. Definition 2. Architecture template. In this chapter, we discuss our hierarchical DSE methodology in a context of the architectures composed respectively with p, m and n number of PEs, SEs and NEs, where the connections between different components as well as the architectural topology (defined by the number and type of NEs) is already fixed. Since such description can be represented by several possible instantiations, we focus specifically on the templates consisting of several homogeneous RISC processors and shared SEs, completed with a few hardware dedicated blocks, in a bus-based architecture. As a consequence, different architecture instances can be derived from the same template by varying the number and type of PEs and SEs, as well as their allocation on the architecture. Assumption 2. We assume that there is a library of configurable resource models for PE, SE and NE, which can be instantiated and configured properly to build the architecture templates mentioned in Definition 2. These components and their parameters of configuration (such as read/write latency, operating frequency, storage capacity, network arbitration policy, and so on) can also be used by the system designer in both estimation (or pruning) phase and simulation phase. For example, using such parameters, a PE can be configured as a generic RISC processor for flexible application support as well as dedicated hardware block for achieving specific performance, while setting appropriately the access latency and storage capacity parameters a SE can behave as a fast cache memory of small storage capacity or memory bank of large storage capacity but high access latency. Definition 3. Mapping. It consists of the process of distributing the application functionality on the available resources of the target architecture. This process implies to address three sub-problems: (i) partitioning: refers to the selection of a suitable PE type for each application’s task, (ii) assignment: decides the type and number of instances for PEs and SEs, their locations in the architecture template, as well as which task and channel should be assigned to which component instance (if more than one instance of a component type is present in the architecture), and (iii) scheduling: defines the order of execution for the different tasks assigned in a PE. Assumption 3. We assume that all application’s tasks are assigned to a set of PEs working in a pipeline fashion, where each PE can execute one task at a time, and task STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 92 duplication and migration are not considered. On the other hand, the inter-tasks synchronizations and communications can be assigned to (i) the SE: when two communicating tasks have been assigned to different PEs, the corresponding inter-tasks channels should be assigned to a shared SE accessible by such two PEs, and therefore a communication delay occurs, or (ii) inside the PE: if two communicating tasks (and their associated inter-tasks channels) reside on the same processor, it then is reasonable to neglect this communication time, without loss of generality. Definition 4. Communication delay or time. The time (in seconds) taken for a communication transaction between a PE and SE is given by the sum of three parts: (i) protocol delay (cpd): latency associated with communication protocol, (ii) contention delay (ccd): waiting time due to simultaneous access attempts to the shared resources, and (iii) SE access delay (rwd): time taken to read/write the data from/to a SE. Definition 5. Computation delay or time. It is the execution time (in seconds) of an application’s task on a specific PE. Thus, all task’s timing information in the pt available types of PE (provided by component library) should de first determined, i.e., each task has a set of computation time {wcet(ti)1, wcet(ti)2, …, wcet(ti)pt}, where wcet(ti)j is the worst-case execution time of task ti on the PE type j. To measure the execution time of a task on a general purpose processor (e.g., ARM), we use an instruction set simulator (e.g., ARM suite developer). Note that the execution time of a specific task on a dedicated hardware implementation is assumed given, while this hardware block takes an infinite amount of time to execute any of the remaining application tasks. As a result, a profile table with pt rows and k columns can be obtained. Assumption 4. We assume that the time required in the communication transactions is much smaller than the execution time. Otherwise, we consider that there is not possible benefit for a parallel implementation of the application in a multiprocessors architecture. Problem statement. Given a real-time application (TG), an architecture template and a component library, our problem is to find the optimal architecture instance for the mapping of the target application, satisfying the RTC and achieving additionally a good triple trade-off among the efficiency in PE usage, PE load balancing and inter-PEs communication traffic minimization. Formally, the optimal mapping solution should satisfy the following design objectives: CHAPTER 4 93 Primary objective The performance of the real-time application mapped on the target MPSoC platform should achieve the RTC. Secondary objectives • Objective 1. Minimize the number of resources used in the mapping solution, i.e.: Min {NPE and NSE} (4.1) where NPE and NSE represent respectively the number of PEs and SEs actually used in the MPSoC platform for mapping the real-time application. • Objective 2. Maximize the efficiency of PEs usage (EPE), i.e.: Max {EPE} (4.2) 100* NP E CMP EPE NPEi i ∑ ∈ = (4.3) where CMPi is the total computation time due to the tasks assigned on PEi. • Objective 3. Minimize the load unbalancing in PEs (LuB), i.e.: Min {LuB} (4.4) 100* NP E )EPECMP(abs LuB NPEi i ∑ ∈ − = (4.5) • Objective 4. Minimize the inter-PEs traffic (IPT), i.e.: Min {IPT} (4.6) 100* d d IPT Dd ij VPLsd qh ij qh ∑ ∑ ∈ ∈ = (4.7) where the denominator represents the total amount of data exchanged by all tasks of the application, while the numerator indicates the amount of data exchanged between tasks STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 94 mapped on different PEs. This latter is denotated as inter-clusters links (VPLs). 4.4 Overview of our hierarchical DSE methodology The overall scheme of our hierarchical DSE methodology is depicted in Fig. 4.2. Two separated phases communicating via a file-based interface can be clearly distinguished: estimation phase and simulation phase. The goal of the first phase is to gradually reduce a large design space to arrive at a reduced number of potential mapping solutions, while the second phase targets a more accurate performance evaluation for each potential solution of this reduced design space. This way, our two-phase approach enables the system designers to exploit (i) the benefits of analytical techniques for a rapid exploration of large design space, (ii) the accuracy of the simulators for individual design point evaluation, and (iii) the ability to integrate different (or additional) analytical models and simulation tools for a hierarchical design space exploration, aiming to solve the problem of the real-time application mapping onto MP-SoC formulated in Section 4.3. As will be explained with more details in the next section, the first phase is based on analytical methods, i.e., this phase does not use simulations, it rather uses a set of heuristic-based algorithms to explore rapidly the design space associated to the subproblems of partitioning, scheduling and assigning, respectively. Moreover, an additional analytical model is used during this process to estimate roughly the performance of each design point (in terms of the computation and communication delay), such that if the resulting delays sum of a design point cannot satisfy the RTC, this design point will not be considered by the simulation phase. As a consequence, our estimation phase can prune dramatically the initial design space, and only a reduced number of potential mapping solutions is given as output. Subsequently, these detected potential solutions are specified in a text file, being the description of each potential solution encoded in a numeric vector (or string) format. This way, each mapping description together with the application model and the architecture template are combined to generate an ESM, which is required and used by the simulator to evaluate more accurately the system performance of each potential solution. Finally, this simulation process is repeated iteratively either until a solution (that meets the user constraints) is found or for all potential solutions, and in this latter case, the optimal simulated solution is then selected as output. CHAPTER 4 95 Fig. 4. 2 Overview of the hierarchical DSE methodology. At this point, we would like to stress that DSE experiments using our hierarchical methodology can be perfectly carried out with NASA framework. In fact, we have performed a set of hierarchical DSE experiments configuring appropriately NASA input files, and plugging CASSE as well as the aforementioned analytical (or pruning) methods into NASA. Evidently, the file-based interfaces used in our hierarchical DSE methodology (see Fig. 4.2) are defined according to the requirement of NASA framework. All the results obtained in these hierarchical DSE experiments are shown in Section 4.6, where we also present a comparative analysis (in terms of run-time and quality of the mapping solutions) between our hierarchical DSE and other DSE based only on analytical models and/or simulations. 4.5 Heuristics-based algorithms and analytical model for hierarchical DSE This section aims at explaining the distinct intermediate steps in each phase of our approach. Moreover, using examples, we illustrate some issues that arise in the process of mapping a real-time application onto a MPSoC. System-level simulator Application task graph Simulation phase system model generator Potential mappings Application specification Real-time constraint Architectural template Select mapping Constraints Satisfied No satisfied Best mapping Abstraction & Speed Evaluation effort & acurracy Components library Tasks clustering HW/SW partitioning Assignment Static performance estimation Estimation phase STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 96 4.5.1 Static performance estimation The goal of this phase is to explore and prune the design space, i.e., identify all potential solutions that meet the design objectives (listed in Section 4.3), while eliminating those alternatives that do not meet the requirements. To this end, an analytical estimation model and three heuristic-based algorithms have been applied currently: (i) HW/SW partitioning, (ii) tasks clustering, and (iii) clusters assignment. 4.5.1.1 HW/SW partitioning For a given TG and available PE types, this algorithm selects a suitable PE type for each task, i.e., it decides whether a task is executed as software embedded on a processor or by using a hardware implementation to achieve specific performance requirements. To this end, all tasks are checked formally by the following condition: wcet(ti)proc ≤ RTC, Tti ∈ ∀ (4.8) where wcet(ti)proc represents the worst case computation time on processor proc for the task ti. Thus, if wcet(ti)proc is longer than RTC, the task ti is selected to run on a processor; otherwise, ti is implemented in a specific hardware block5. As a result, this partitioning algorithm outputs two numeric vectors or strings: VNT and VCT. Tasks A B C D 1(proc) 20 5 5 2 wcet for each PE type 2(HW) 10 - - - VCT 10 5 5 2 Partitionning outputs VNT 2 1 1 1 Fig. 4. 3 Example of the HW/SW partitioning algorithm. 1) VNT is a vector containing the nature of each task. In this context, the nature of the task refers to the PE type selected for each task, i.e., hardware dedicated block or generic processor. Note that the VNT is actually a numeric vector, such that different types of PEs (e.g., processors and/or hardware dedicated blocks) are coded with different numeric values. 5 We assume that the computation time of the task ti on a dedicated hardware block can perfectly satisfy the aforementioned condition. 2 1 A C B D 1 1 RTC = 14 u.t CHAPTER 4 97 2) VCT is a vector defined as {c(t1), c(t2), …, c(tk)}, where c(ti) is the computation time of task ti on the PE type selected for ti, i.e., according to the nature of the task ti specified in VNT. Example 4.2. Fig. 4.3 depicts an application modelled as a task graph composed of 4 tasks and 4 channels. Suppose that 2 PE types are available in the component library: a generic processor (proc) and a HW dedicated block for task A, and RTC is 14 u.t. Then, according to the wcet values listed in Fig. 4.3 and (4.8), the HW/SW partitioning algorithm will select the task A for a hardware implementation, while the rest of the tasks will be run on the generic processor. As a consequence, the VNT and VCT will be delivered as outputs, which are also shown in Fig. 4.3. Finally, it should be noticed that no information about architecture topology/platform is taken into account in this step. 4.5.1.2 Tasks clustering This step aims to solve the sub-problem of scheduling. Basically, we propose an algorithm that, considering the RTC, the outputs of the partitioning algorithm, and the data dependencies between tasks specified in TG, enables to schedule the tasks on v logical clusters or Virtual Processors (VPs) working in a pipeline fashion, such that each task (inside a VP) is executed according to the order in which it was scheduled in the VP. The pseudo-code of our tasks clustering algorithm is described in Algorithm 1. First, the clustering algorithm uses the information contained in VNT to bind each task selected for hardware implementation to a new VP. Subsequently, it creates a new task graph (TG’={T’, L’, D’}) without the tasks bound to VPs. Note that all links associated to such bound tasks are not considered in TG’. Then, the clustering algorithm copies all links of the roots to the list of ready-links (R), such that each couple of tasks associated to each link of R that satisfies the two following conditions are bound to the current virtual processor (namely, VPh): ))VP((cRTC)t(c)t(c hji ν − ≤ + (4.9) ⎭ ⎬ ⎫ ⎩ ⎨ ⎧+∑ ∈∀ ∈∀ )t(succt jkij Rl|d jk ijij d}d{maxmin (4.10) where )VP( h ν gives the set of tasks that are bound on VPh. The first condition ensures STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 104 Fig. 4. 5 Example of the cluster assignment algorithm and analytical estimation. Our idea is that, the contention delay suffered by an inter-clusters link is directly proportional to the average SE access delay of the VPLs that compete for the same NE, such that the more VPLs (i.e., a high α value) share the same path, the more waiting-time (on average) is needed to access the data. However, we also would like to notice that, this way of estimating the contention delays can introduce certain error or difference with respect to the simulation results when, (i) the SE access delay of inter-clusters links (sharing the same NE) present high deviations with respect to the average SE access delay, and/or (ii) the number of inter-clusters links sharing the same NE increases, as will be depicted in the Section 4.6. mem pe2 bus pe1 bff mem pe2pe2 bus pe1 pe1 bff Latency table bff(2) mem(3) pe1 0 1 pe2 0 1 VPs mapping VPLs mapping CMM Possible mapping VP1 VP2 VPL1(1) VPL2(2) Feasibility pe1 pe2 max{CMMi+CMPi} 1 bff bff Infeasible(1) - - - 2 bff mem Infeasible(2) 2 2 14 3 mem bff Feasible 1 1 13* 4 pe1(HW) CMP(pe1)=10 pe2(proc) CMP(pe2)=12 mem mem Infeasible(2) 4,5 4,5 16,5 5 bff bff Infeasible(1) - - - 6 bff mem Infeasible(2) 2 2 14 7 mem bff Feasible 1 1 13 8 pe2(HW) CMP(pe2)=10 pe1(proc) CMP(pe1)=12 mem mem Infeasible(2) 4,5 4,5 16,5 Infeasible(1): Storage capacity limitation; Infeasible(2): Violation of VPLs assignment constraints; * For sake of simplicity, we suppose that cpd=0; {} { } ;CMPCMMmax;..iRTCCMPCMMmax ;CMMCMP;CMM ;ccd ; ;)bus(com ;rwd pe ;CMMCMP;CMM ;ccd ; ;)bus(com ;rwd pe ii 141321 131 0 1 1 11120 2 111 0 1 1 11120 1 22 222 211 ≤=+⇒=∀≤+ =+= ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ = ⎭ ⎬ ⎫ = = =×+×= ⇒ =+= ⎪ ⎭ ⎪ ⎬ ⎫ ⎪ ⎩ ⎪ ⎨ ⎧ = ⎭ ⎬ ⎫ = = =×+×= ⇒ α α CHAPTER 4 105 Once that all CMMi have been estimated according to the aforementioned process, our algorithm eliminates all those scenarios that do not satisfy the condition (4.12). As a result, the remaining scenarios are ranked and listed in the ascendant order of the maximum total PE time, such that a scenario with a small maximum total PE time is evaluated first in the next simulation-based phase. 4.5.2 Potential solutions In our framework, a text-file interface is used to link both estimation and simulation phases. Such interface enables to represent symbolically the design space composed by the potential solutions, where each alternative is encoded as two numeric strings. The format of these strings is described as the following: {idPE1, idPE2,…, idPEk; idSE12, idSE13,…, idSEjk} {tPE1, tPE2,…, tPEp; tSE1, tSE2,…, tSEm} where idPEk indicates that the task tk is mapped on the PE holder idPE, idSEjk refers that the link ljk is mapped on the SE instance holder idSE, while tPEp and tSEm represent the PE instance type and the SE instance type allocated in PE holder p and SE holder m, respectively. Fig. 4.6 illustrates an example of such strings, which correspond to the case studied in the above examples. Fig. 4. 6 Example of mapping solution description strings. It should be noticed that the choice of the representation (or encoding) scheme has a strong impact on the scalability and flexibility of the framework. And in our case, this choice is due to mainly three reasons: (i) it allows us to modularly define a very large space, where our representation scheme warrants that each potential solution receives a unique encoding value, 1 2 2 2 1 2 0 0 Tasks Channels 1: pe1 2: pe2 idPE 0:intraPE 1: SE1 idSE 2: SE2 1 2 1 2 PEs SEs 1: HW 2: p roc tPE 1:mem 2: bf f tSE STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 106 (ii) both the vector length and the variable values are not fixed, but they are dynamically updated for each experiment according to the user specifications, and (ii) last but not least, this format fits perfectly to the interface requirements of NASA. This way, our hierarchical DSE methodology as well as our analytical algorithms can be plugged into NASA infrastructure, as will be demonstrated in Section 4.6. 4.5.3 Global system simulation In order to evaluate more accurately each potential solution of the pruned design space, we have used CASSE in our framework. As explained in Chapter 2, CASSE enables the system designers to include and configure (for each DSE experiment) numerous design variables, which often are not taken into account by the analytical models, such as bus arbiter policy, processor scheduler, memory map, different clock domains, size and number of data packets that can simultaneously circulate on the network, and so on. As a result, different quantitative information about the studied system can be gathered during each simulation, which provides to the system designer a more complete and realistic vision of the system load fluctuations, as well as their impact on the system performance for later evaluation and final decisions. In this point, it should be noticed that in order to simulate each potential solution, the simulatable system model of each potential solution (i.e., an ESM consisting of an application model7, architecture model and mapping model) should be generated first. To this end, we have used the Translator (presented in Section 3.5.5), which can carry out automatically this process, as already explained in Chapter 3. Evidently, the needed information about the task computation delay, as well as the number and type of each kind of components in the architecture are provided by the potential solution strings explained in Section 4.5.2. Finally, each potential solution is evaluated in CASSE, where we use a pre-determined terminating condition to conclude the system-level simulations. Thus, the iterations eventually terminate either when a solution meeting the real-time requirement is found, or when no potential solution can achieve such user constraint. On the latter case, no solution is output by our approach. 7 Note that the estimation phase only needs the task-graph (TG) of the application to carry out the design space exploration and pruning process, while the source code of the tasks is required explicitly by CASSE to perform the system-level simulations. CHAPTER 4 107 4.6 Experimental results In this section, we present several sets of experimental results. Our aim is to compare our hierarchical DSE approach with other approaches based only on analytical model or on simulation tool, and therefore demonstrating the capacities and benefits of using our mixed and hierarchical approach for the kind of problem addressed in this chapter. Finally, we also would like to stress that all our DSE experiments are carried out with the NASA framework, illustrating thus its flexibility and capacity to integrate different kinds of techniques for performing system-level DSE experiments, as well as to solve the mapping problem taking into account multiple design objectives, as formulated in the problem statement of Section 4.3. 4.6.1 Analysis of the DSE efficiency 4.6.1.1 Target MPSoC platform and real-time application The studied architecture template, the latency table associated to such template, as well as the possible configuration parameters of the different architectural components are depicted in Fig. 4.7. Basically, this MP-SoC template may consist of up to 6 PEs of types ARM-9 or hardware blocks, up to 3 SEs of either single (SDR) or double (DDR) data rate types, and up to 2 AMBA busses. The application that is mapped onto the MP-SoC is the visual tracking algorithm presented in Chapter 2. 4.6.1.2 NASA configurations for DSE experiments Using such user specifications, we have configured NASA to perform several sets of experiments. In the first set of experiments, only the estimation phase (i.e., analytical estimation model) of our hierarchical approach has been used to find the optimal mapping. Since no simulations are needed in this set of experiments, it can be carried out without using CASSE. Note that a single solution (or the best estimated solution) is outputted in this case. Subsequently, we repeat the set of experiments using our twophase approach. To this end, we have plugged into NASA both our analytical models and CASSE. In addition, we performed the last set of DSE experiments using two genetic algorithms (GAs), i.e., we apply our dimension-oriented DSE methodology (presented in Chapter 3) in order to co-explore the design space (consisting of the architectural components and mapping dimensions). It should be noticed that the platform dimension is not explored in these experiments since the MPSoC platform is already fixed, so that we had to set up appropriately the platform string values according to the template depicted in Fig. 4.7. Finally, the values of the GA parameters used in this last set of experiments are listed in Table 4.1. STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 108 bff1 (128) bff2 (128) SE1 (Cap) SE2 (Cap) SE3 (Cap) PE1 0 ∞ Lat Lat Lat PE2 0 0 Lat ∞ ∞ PE3 ∞ 0 Lat Lat Lat PE4 ∞ ∞ Lat ∞ ∞ PE5 ∞ ∞ ∞ Lat Lat PE6 ∞ ∞ Lat Lat Lat Architecture element Number Types Value RISC ARM-9 PE ≤ 6 Accelerator Dedicated hardware SDR Cap=256 KB; Lat=5 SE ≤ 3 DDR Cap=28 KB; Lat=1 NE ≤ 2 AMBA bus 32 bit width, Round robin arbiter, I/O buffered Fig. 4. 7 Target architecture template and component configuration parameters. Table 4. 1 GA parameters used in the third set of experiments. 4.6.1.3 Comparisons between different DSE approaches In order to compare the experimental results obtained with different DSE approaches, we have selected four metrics: (M 1) Number of explored design points. (M 2) Total run time of the DSE experiment. (M 3) Performance achieved by the optimal solution found in the exploration. (M 4) Number of simulations until finding the optimal solution. The most significant differences between the results obtained in the aforementioned experiments are summarized in Table 4.2. At first sight, it can be seen that for different PE1 PE2 SE1 NE1 NE2 PE3 PE4 PE5 PE6 bff1 bff2 SE3SE2 Parameters Number Types Values Selector (S) 1 1 Proportional with elitism Crossover (C) 1 2 2-points C probability (pc) 5 - [0.1, 0.3, 0.5, 0.8, 1.0] Mutation (M) 1 1 Single mutation per individual M probability (pm) 5 - [0.1, 0.3, 0.5, 0.8, 1.0] Population size 10 - Nr. of individual per iteration Iterations 21 - - CHAPTER 4 109 timing constraints (RTC = 25 frames/s and RTC = 28 frames/s, i.e., processing 1250 packets/s and 1400 packets/s, respectively), our hierarchical DSE approach not only can cover statically a large number of design points, but also can achieve a valid solution after only a reasonable small number of simulations. On the other hand, if only the analytical phase is applied in the DSE experiments, a large design space can be also explored analytically. However, a more accurate evaluation reveals that the best estimated solution (which achieves the real-time requirement according to the analytical model) cannot always satisfy actually such constraints (for example, as in the case of RTC = 28 frames/s). As already mentioned in Section 4.1.3, such difference or margin between the estimated and simulated result is inherent in any analytical estimation model, what emphases the need of a simulation-based phase in our approach. Table 4. 2 Comparison of the DSE efficiency between the three sets of experiments. Finally, the DSE in the last set of experiments is guided by two GAs, which ensures the convergence to the optima points exploring only a reduced number of alternatives, as has already been demonstrated in Chapter 3. Note that a GA could have substituted perfectly our heuristics-based algorithms at the pruning phase as well. This way, an exhaustive exploration of all possible design combinations (in the assignment step) is not needed any more, therefore improving greatly the efficiency of our DSE experiments. However, in spite of the efficiency demonstrated in our GA-based DSE experiments, the long simulation time is still being the dominant factor in these experiments based only on simulations. In fact, CASSE requires on average 30 seconds to simulate a single design point in these experiments, while the GAs need an average time of 1800 seconds and 6000 seconds (i.e., for 60 and 200 simulations) to reach the first solution that meets the real-time constraints of 25 frames/s and 28 frames/s, respectively. That is, comparing with GAs-based DSE experiments, our hierarchical DSE approach can improve the efficiency of DSE (in terms of total run-time to reach the first valid mapping) by two orders of magnitude. Moreover, we also would like to notice that the results obtained in GARTC = 25 frames/s RTC = 28 frames/s M 1 M 2 M 3* M 4 M 1 M 2 M 3* M 4 Estimation 279936 30 s 1252 (1266) - 279936 30 s 1308 (1425) - Estimation + Simulation 279936 30 s 1252 (1266) 1 279936 90 s 1401 (1411) 3 Simulation 210 1800 s 1263 (-) 60 210 6000 s 1408 (-) 200 * Performance obtained in the simulation (estimation). STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 110 based experiments suffer from an important variance, since the GA is extremely sensitive to its parameters such as the initial population, probability associated to crossover (pc) and mutation (pm) operator, etc. This last aspect can be illustrated in Fig. 4.8, where the gray dotted lines indicate the top and down boundaries closing the results obtained with 40 different initial populations and combinations of pc and pm, the black line represents the average performance in each iteration reached by the individuals of all GA-based experiments, while the gray lines are two particular examples extracted from this set of experiments. If the input arrival frame rate is 1450 packets/s and a minimum of 1250 packets/s has to be processed to satisfy the minimum RTC of the studied application (which is equivalent to processing 25 frames/s), it can be seen clearly that, the experiment labelled pc=0.8pm=0.8 not only needs fewer simulations to reach a valid solution, but can also converge progressively to higher performance solutions, while the other experiment labelled pc=0.5pm0.1 can hardly reach the minimum RTC after 20 iterations. 400 600 800 1000 1200 1400 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Iterations Performance (packets/s) Maximum Minimum pc0.5pm0.1 pc0.8pm0.8 Average Fig. 4. 8 Results obtained in GA-based DSE experiments. Moreover, the variation of the performance achieved in DSE experiments with different GA parameters configurations can be significant. And for the case shown in Fig. 4.8, such a margin between the maximum and minimum can be up to 65% (measured in sixth iteration). In our point of view, these data could suggest that, in order to find out the best configuration of the GA parameters for each studied case, the system designers should repeat the experiments several times with different combinations of GA parameters settings, therefore decreasing the attraction (in terms of time and efforts) of using GA in the DSE experiments. CHAPTER 4 111 4.6.2 Analysis of the quality of the optimal solutions In this point, it also should be noticed that although our hierarchical DSE approach and GA-based DSE experiments can provide solutions satisfying different RTCs (i.e., primary design objective), the quality of such solutions can be also radically different. In this context, we measure the quality of the solution in terms of the secondary design objectives defined in Section 4.3, i.e.: (O 1) Minimize the resources used in the architecture design. (O 2) Maximize the efficiency of resource usage. (O 3) Minimize the load unbalancing between PEs actually used in the solution. (O 4) Minimize the total communication traffic in the system. In Table 4.3, we list the mapping solutions obtained by our hierarchical DSE approach, as well as the first optimal mapping solution reached by the GAs-based experiment pc0.8pm0.8 for different RTCs. More specifically, we indicate the type of PE and SE allocated in the component holders actually used in each solution, as well as the tasks and channels mapped on each of them. On the other hand, Table 4.4 analyzes the quality of the aforementioned solutions in terms of the aforementioned secondary design objectives. Table 4. 3 Mapping solutions obtained in our DSE experiments. Examining these data, it can be seen that for both RTCs, our approach of hierarchical and mixed estimation and simulation DSE can provide solutions using a lower number of PEs and SEs. On the other hand, the number of assigned PEs has also a direct impact on the system traffic (i.e., O 4) , since the more PEs are used, the less amount of interRTC (frames/s) Tasks mapping Channels mapping Estimation + Simualtion Proc1={A}, HW3={D}, Proc2={B,C,E,F,G} Buf1={1}, Buf2={3,4,5,9,10} 25 Simulation Proc1={B,C}, Proc3={E}, HW5={D}, Proc4={A,F,G} SDR1={1,6,7,9,11,12}, DDR2={3,5,10}, DDR3={4} Estimation + Simulation Proc1={A}, HW3={D}, Proc2={B}, Proc6={C,E,F,G} Buf1={1}, Buf2={3}, DDR1={2,9,10}, DDR2={4,5} 28 Simulation Proc1={B}, Proc5={C}, HW4={D}, Proc3={F,G}, Proc6={A,E} SDR1={3,6,10,11}, DDR2={2,7,9}, DDR3={1,4,5} STRATEGY AND ALGORITHMS FOR MAPPING REAL-TIME APPLICATION ONTO MPSOC 112 tasks channels are assigned inside PEs, therefore increasing the volume of exchanged data via shared resources and lengthening the actual execution time of the tasks. In fact, an immediate effect of this latter result is also visible on the difference of performances obtained in the estimation and simulation, shown in Table 4.2. In this case, when the number of resources competing for shared resources increases, the occurrence of contention becomes probably more frequent and complex. As a result, the performance estimated with the analytical model is less accurate, increasing the margin between estimated and simulated results. Table 4. 4 Comparison of the quality of the mapping solutions. To summarize, RTCs can be easily achieved by over-dimensioning the hardware resources, as occurs with the results obtained in GAs-based DSE experiments. However, the challenge is to deliver timing guarantees without such forms of over-provisioning, because this latter tends to introduce larger amounts of traffic load and/or repetitive overhead, saturating thus the system communication. Therefore, the results illustrated in this section reveal that our proposed methodology is profitable for searching/exploring large design spaces. More specifically, compared with the traditional GA-based search techniques, our hierarchical DSE methodology can improve the efficiency of DSE by two orders of magnitude as well as provide higher quality mapping solutions. However, we would like to stress that these proof-of-concept DSE experiments are aimed to demonstrate and illustrate the key properties of our methodology for a target application and a particular MPSoC platform. Then, we plan to carry out more experiments using more applications and a wide range of architectures in the future, in order to validate and prove progressively the capabilities of the methodology presented in this chapter. RTC (frames/s) O 1* O 2 O 3 O 4 Estimation + Simualtion 3 (0) 88.875 % 11.533 % 49.045 % 25 Simulation 4 (3) 66.656 % 29.066 % 87.308 % Estimation + Simulation 4 (2) 71.655 % 18.427 % 58.903 % 28 Simulation 5 (3) 57.324 % 30.026 % 97.124 % * Number of PE (SE) used in the solution. CHAPTER 4 113 4.7 Conclusions With the increasing complexity of embedded systems on chips, an enormous amount of new possibilities for the application mapping onto a target architecture is emerging, leading to an exponential growth of the design space. Such challenge demands new methodology capable to explore large design space in a fast and accurate way. In this chapter, we have focused on the problem of the mapping of a real-time application on a flexible architecture template, and more specifically, we have presented a hierarchical DSE methodology and a set of analytical methods to address this issue. We consider that the set of experiments conducted are quite complete and enough to prove the concept and to validate the framework, setting up the road for more experiments in the future in order to progressively show the full capabilities of our methodology. Our proposed methodology consists of two independent phases. The first phase uses a set of heuristic-based algorithms for the design space exploration, as well as an analytical model for a rough performance estimation of the explored design points. The purpose of this phase is to prune rapidly a large design space, such that only a reduce number of potential solutions are retained for next phase. Then, a system-level simulation tool is used in the second phase, in order to evaluate accurately each of these selected solutions until a solution meeting RTC is found. Finally, the experimental results presented in this paper reveal that our approach, compared to other approaches based only on either analytical estimation models or on simulations guided by GAs, not only can explore a large design space and reach a valid solution in a time-efficient and accurate way, but can also provide an optimal solution optimizing features such as resource usage efficiency, system traffic load and processor load balancing. Chapter 6 Resumen en español En este capítulo presentamos un resumen en español del contenido de esta tesis. 125 Resumen medida que la capacidad de integración en chip aumenta, los sistemas en chip (SoC) se vuelven cada vez más complejos, siendo bastante habitual en la actualidad encontrarnos con SoCs que integran una gran variedad de elementos de procesamiento, memorias, dispositivos I/O y elementos de comunicación. Para hacer frente a la complejidad de diseño de los modernos SoCs, los diseñadores de sistemas propusieron elevar el nivel de abstracción del proceso de diseño al nivel de sistema, donde la exploración del espacio de diseño (DSE) se ha convertido en una pieza clave en el proceso de diseño a nivel de sistema (SLD). Sin embargo, cabría preguntarse en este contexto si las metodologías de diseño existentes permiten al diseñador explotar todo el beneficio potencial de la DSE a nivel de sistema, o si se deberían plantear nuevas metodologías y/o técnicas alternativas para sacar el máximo provecho del SLD. Esta tesis pretende precisamente responder a dicha cuestión. Concretamente, hemos desarrollo nuevas metodologías y novedosos algoritmos con el objetivo de aminorar el esfuerzo del diseñador de sistemas y lograr eficientes DSE en la etapa temprana del proceso de diseño. Asimismo, con el fin de validar nuestras técnicas y esquemas de trabajo, también hemos presentado una importante cantidad de experimentos de DSE en esta tesis. Estos resultados experimentales demuestran que, en comparación con las metodologías tradicionales, nuestras propuestas no sólo pueden mejorar la productividad del diseñador y la eficiencia de DSE a nivel de sistema, sino que también son capaces de obtener diseños de mayor calidad. A RESUMEN EN ESPAÑOL 126 6.1 Introducción El mundo está cambiando. Este hecho es aplicable a una gran variedad de aspectos de nuestro entorno, pero desde mi punto de vista, es en el ámbito tecnológico donde toma su máxima expresión. Sin embargo, a pesar de que los avances tecnológicos están introduciendo cambios en nuestras vidas, aportando nuevas fórmulas y soluciones optimizadas, también abren puertas a nuevos desafíos que esperan resolución. Desde el punto de vista de los clientes tecnológicos (ya sean éstos los consumidores finales o consumidores intermedios), exigen cada vez más innovación y más funcionalidades. Este apetito feroz por lo más innovador no se debe a otra cosa que el propio avance de la tecnología, provocando una situación paradójica conocida como ciclo vicioso. Es decir, los consumidores siempre están demandando productos innovadores, porque lo que hace poco era innovador pasa a considerarse obsoleto tras un cierto periodo de tiempo relativamente corto, con lo cual el fabricante está obligado a recurrir al ingenio y a buscar soluciones para satisfacer estas necesidades, que terminan casi siempre colocando en el mercado un producto nuevo o una versión mejorada; y así se repite este mismo ciclo una y otra vez. Desde el punto de vista de los productores tecnológicos, que abarcan desde las instituciones públicas y privadas hasta los fabricantes (es decir, todos aquellos que contribuyen a estos avances), cabrían dos tipos de reflexiones. Por un lado, para aquellos situados en la orilla empresarial de este sector, el anterior ciclo vicioso se convierte en un ciclo virtuoso, puesto que la constante demanda del mercado se traduce en unos clientes fieles y mercados cautivos, y en definitiva, les garantizan tener siempre un trozo del pastel. No obstante, desde el punto de vista de los verdaderos productores tecnológicos, es decir, las cabezas pensantes, el ciclo vicioso representa un verdadero desafío. Por otro lado, este desafío no sólo proviene desde el lado de la demanda, sino también existen presiones desde el lado de la oferta. Esto último se traduce en que los diseñadores no sólo deben dar con la solución del problema planteado por los consumidores, sino que también dicha solución debe satisfacer al mismo tiempo unas restricciones empresariales (costes, time-to-market, tecnología disponible, economía de escala/alcance, etc.) Desafortunadamente, los modelos tradicionales de diseño CHAPTER 6 127 presentan cada vez más dificultades para conseguir la convergencia de ambas fuerzas, y consecuentemente, deben considerarse nuevas metodologías y herramientas de trabajo. 6.1.1 Diseño a nivel de sistema 6.1.1.1 Ventajas del diseño a nivel de sistema Como se mencionó en el apartado anterior, las constantes demandas de nuevas funcionalidades exigen que los diseños sean cada vez más complejos, y esto último se traduce en lo que respecta a los diseñadores en escribir más líneas de código. Esto es, lo que antes era un componente muy sencillo, ahora se convierte en un procesador, y lo que inicialmente era un aglomerado de componentes pasa a ser un sistema multiprocesador completo. No obstante, los esfuerzos de los diseñadores no sólo se centran en el diseño, sino también en el tiempo dedicado a la simulación y la verificación. Si a esto último se le suma que la innovación es constante, entonces esa dimensión del esfuerzo se magnifica en términos descomunales. En respuesta a estos desafíos, numerosos investigadores propusieron elevar el nivel de abstracción para el modelado, simulación y verificación del diseño. Trabajar a un mayor nivel de abstracción (pasando del RTL a nivel de sistema), aparte de manejar las informaciones con un mayor nivel de granularidad, ciertamente presenta otras importantes ventajas para el diseñador: Reducción del esfuerzo. A nivel de sistema, el diseñador puede trabajar directamente con macro-bloques o componentes predefinidos, los cuales muchas veces son proporcionados por las propias librerías de las herramientas de trabajo, como ya se explicará más adelante. Estos componentes ya prediseñados (y verificados) proporcionan las prestaciones y funcionalidades necesarias al diseñador. Por consiguiente, con ellos los diseñadores pueden centrar sus esfuerzos en configurar y organizar el conjunto de macro-bloques para que realicen correctamente sus cometidos, ahorrando así tiempo y evitando duplicar esfuerzos innecesarios. Mayor flexibilidad. Los componentes de las librerías son básicamente plantillas de diferentes tipos de recursos que podemos encontrar en cualquier sistema. Entre otros se tratan de elementos de procesamiento (PEs) que modelan el comportamiento de los procesadores, DSP, coprocesadores y aceleradores. Asimismo, también se pueden encontrar los elementos de almacenamiento (SEs), que pueden configurarse como diversos tipos de memorias. Finalmente, los elementos de comunicación (NEs) prestan RESUMEN EN ESPAÑOL 128 servicios de comunicación para los elementos que están unidos a ellos. Como todos estos elementos son altamente configurables a través de los parámetros asociados a cada uno ellos, podemos derivar fácilmente desde un diseño a otro sin más que reconfigurar dichos parámetros. Abstracción de los detalles. Cuando el sistema crece, crece también el conjunto de detalles que el diseñador debe tener presente. Por ejemplo, cuando se modela un sistema en chip (SoC) compuesto de varios PEs, numerosas SEs y una estructura de comunicación multi-bus, el trabajo del diseñador de sistema está orientado a que el conjunto de estos elementos tengan el comportamiento esperado, es decir, que los PEs transfieran sus datos correctamente a las SEs que tienen acceso y asegurar el uso correcto del NE compartido evitando los problemas de contención. En definitiva, se centran en las informaciones a nivel de bloques y no tanto en lo que suceden dentro de cada uno de ellos. Menor tiempo de simulación. Para trabajar a un mayor nivel de abstracción, también se precisa una nueva generación de herramientas de diseño y simulación para explotar al máximo todas las ventajas comentadas. Uno de los aspectos a destacar de estas herramientas es su esquema de simulación. A diferencia de los tradicionales simuladores para RTL, estos nuevos simuladores trabajan a nivel de transacciones (TLM). Trabajando a este nivel, el diseñador puede abstraerse de numerosos detalles de implementación, dando como resultado que las simulaciones sean mucho más rápidas. Todas estas características justifican en gran medida el por qué de la emigración del nivel de trabajo o modelado de los diseñadores de sistema. No obstante, si bien es verdad que estas contribuciones pueden facilitar y acelerar el proceso de diseño, también implican nuevos desafíos no estudiados hasta la fecha, obligando a los investigadores a ofrecer soluciones acordes a estas exigencias. 6.1.1.2 Metodologías de diseño a nivel de sistema Con el incremento de la complejidad de los sistemas se pone en evidencia cada vez más la ineficiencia de los esquemas basados en el flujo de co-diseño hardware/software, que si bien su aplicación sigue siendo posible en los complejos SoCs actuales, el esfuerzo y el coste requerido hace que esta opción sea cada vez menos atractiva. CHAPTER 6 129 Como consecuencia, en los últimos años se han seguido tres estrategias en la construcción de flujos de diseño de estos sistemas siguiendo el mismo tipo de pautas que, anteriormente se empleaban a nivel RTL: flujos de diseño top-down, meet-in-themiddle, y bottom-up. La metodología basada en el flujo de diseño top-down sigue una trayectoria descendente. En ella, partiendo de unos requerimientos y especificaciones del sistema, el diseñador modela el sistema y, a continuación, va refinando progresivamente desde ese modelo lógico hasta llegar a una implementación física. En cambio, el flujo de diseño bottom-up es justo lo contrario que el caso anterior. En este caso, el diseñador parte de una cierta implementación física ya definida, y va abstrayendo hacia niveles de abstracción superiores hasta encontrar con la aplicación que mejor se ajusta a estas características físicas. Finalmente, el flujo meet-in-the-middle es un caso intermedio entre los dos anteriores, es decir, no se trata de un top-down ni de un bottom-up en sentido estricto. En este caso, el diseñador también parte de unos requerimientos y especificaciones de alto nivel, pero a su vez dispone de una determinada arquitectura configurable, por lo que el diseñador refina por un lado la aplicación y por otro va subiendo de nivel de abstracción, hasta que ambos procesos se encuentren en un punto intermedio. Formalmente, existen unos conceptos que subyacen tras cada una de estas metodologías. En este ámbito se puede hacer referencia a la síntesis de alto nivel, el principio de la ortogonalización y el diseño basado en componentes. En el proceso de síntesis, el diseñador añade progresivamente detalles de diseño hasta lograr una solución física concreta. A pesar de utilizarse ampliamente en la actualidad, el principal inconveniente es su carácter ad-hoc, careciendo de la flexibilidad y reconfigurabilidad que comentábamos en los párrafos anteriores. Al mismo tiempo, la reciente tendencia de diseño basado en componentes aprovecha la disponibilidad de un conjunto de elementos ya predefinidos, y así, mediante la composición con los mismos, se obtiene el diseño del sistema que mejor se ajusta a las especificaciones de la aplicación. Finalmente, el concepto de ortogonalización propone la separación de la funcionalidad y la implementación y la computación de la comunicación, permitiendo de esta forma mayor libertad e independencia entre las diferentes etapas del proceso de diseño, ganando un tiempo valiosísimo con este planteamiento de trabajo en paralelo. RESUMEN EN ESPAÑOL 130 6.1.2 Exploración del espacio de diseño a nivel de sistema 6.1.2.1 Los objetivos de la exploración del espacio de diseño Otra consecuencia del incremento de la capacidad de integración en chip es el crecimiento exponencial del espacio de diseño que el diseñador de sistema debe gestionar. En este contexto, un espacio de diseño se compone de un conjunto de puntos de diseño, donde cada uno de ellos representa una solución de diseño definido por diferentes decisiones u opciones de diseño, tales como la partición HW/SW, el mapeo de la aplicación, la topología de la plataforma arquitectural, el número y tipo de cada uno de los componentes de la arquitectura, etc. Evidentemente, cuanto mayor es el número de decisiones de diseño que debe tener en cuenta el diseñador, mayor será el espacio de diseño a explorar, y por consiguiente, mayor será el esfuerzo que conlleva al diseñador para encontrar una solución óptima de diseño. Precisamente debido a todo lo comentado anteriormente, podemos afirmar que la exploración del espacio de diseño (DSE) a nivel de sistema se ha convertido en una tarea clave para el modelado y diseño de los sistemas empotrados modernos. A grandes rasgos, los principales objetivos del DSE a nivel de sistema es explorar grandes espacios de diseño de una forma eficiente y eficaz, y analizar distintos puntos de diseño en términos de un conjunto de métricas (tales como consumo de potencia, costes/área y prestaciones) con el fin de encontrar la solución óptima de diseño que satisfaga los objetivos especificados por el diseñador. Por otra parte, además de explorar una amplia gama de opciones de diseño, la DSE también permite que los diseñadores puedan analizar el impacto o la influencia de diferentes decisiones de diseño en el comportamiento global del sistema y, de esta forma, tomar las decisiones de optimización mucho antes de que el diseño final esté disponible. Por lo tanto, podemos afirmar que una correcta DSE en una etapa temprana de diseño tiene suma relevancia en el éxito o el fracaso del producto final. Además, contribuye también al ahorro de tiempo y esfuerzo en el proceso de diseño, puesto que evita que los diseñadores tengan que trabajar sobre unas soluciones sin posibilidad de ajustarlas a los requerimientos de diseño debido a decisiones de diseño inadecuadas de partida. 6.1.2.2 Los componentes de la exploración del espacio de diseño El proceso de DSE a nivel de sistema consiste en tres componentes interdependientes: (i) el método de búsqueda para viajar por el espacio de diseño de forma sistemática, (ii) la técnica de evaluación para analizar la calidad de cada punto de diseño seleccionado CHAPTER 6 131 por el método de búsqueda, y (iii) un mecanismo para generar la descripción del sistema que utiliza la técnica de evaluación para proporcionar las métricas necesarias. La interdependencia resultante entre estos tres componentes se muestra en la Fig. 1.1. 6.1.2.2.1 Los métodos de búsqueda Se pueden mencionar dos tipos de métodos: estrategias para cubrir el espacio de diseño y los métodos que podan el espacio de diseño. Cabe señalar que ambas categorías pueden aplicarse de forma independiente o conjuntamente para llevar a cabo una DSE. De hecho, el Capítulo 4 de esta tesis presenta una metodología para DSE a nivel de sistema que combina técnicas pertenecientes a ambas categorías con el fin de mejorar la eficiencia de la DSE, como se explicará más adelante. Estrategias para cubrir el espacio de diseño Se pueden mencionar tres tipos de estrategias en este bloque: búsqueda exhaustiva, al azar y guiada. Mientras que las dos primeras técnicas se suelen implementar mediante un script de control específico para cada experimento de DSE (lo que les hacen inflexibles y difícilmente reutilizables), la búsqueda guiada se basa normalmente en la heurística. • Evaluar de forma exhaustiva todos los puntos de diseño. Este enfoque evalúa todas las combinaciones posibles de los parámetros de diseño, por lo que es prohibitivo para aplicarse en grandes espacios del diseño. Aunque el espacio de diseño se puede reducir limitando la gama de parámetros de diseño, este tipo de búsqueda se lleva acabo sin ningún tipo de guía ni tampoco teniendo en cuenta las preferencias del diseñador. • Muestreo aleatorio del espacio de diseño. Seleccionar y evaluar muestras aleatorias es una opción apropiada para explorar grandes espacios del diseño e intentar identificar tendencias. Además, este tipo de técnica también tiene la ventaja de que presenta una perspectiva imparcial sobre las características del espacio de diseño. • Incorporar conocimientos acerca del espacio de diseño. Las estrategias de búsqueda en esta categoría incorporan conocimientos acerca del espacio de diseño en el proceso de búsqueda, con el fin de asegurar la convergencia hacia soluciones óptimas. El conocimiento puede actualizarse en cada iteración del proceso de búsqueda o puede ser una característica inherente del algoritmo de búsqueda. RESUMEN EN ESPAÑOL 132 Métodos que podan el diseño del espacio Todos los métodos de exploración mencionados anteriormente pueden emplearse conjuntamente con las técnicas presentadas en este apartado, con el fin de reducir la complejidad de la búsqueda. • Exploración jerárquica. Normalmente, este proceso se centra en eliminar rápidamente aquellos puntos de diseño que no pueden satisfacer las especificaciones de diseño, en lugar de asegurar una evaluación detallada de cada alternativa de diseño. En consecuencia, el conjunto de soluciones candidatas seleccionadas por el proceso anterior se evalúan con un mayor nivel de detalle por las herramientas de simulación en una fase posterior. • Submuestreo del espacio de diseño. El submuestreo del espacio de diseño es una opción razonable si el diseñador está interesado en una DSE objetiva o cuando la búsqueda exhaustiva es prohibitiva. El patrón de submuestreo podría establecerse completamente al azar, basándose en algún tipo de patrón o función objetivo. 6.1.2.2.2 Las técnicas de evaluación La esencia de las técnicas de evaluación es proporcionar un conjunto de métricas sobre la calidad de los sistemas o soluciones de diseño a los métodos de búsqueda y diseñadores, con el fin de que éstos últimos influyan en la toma de decisiones en el proceso de búsqueda de DSE. Para la DSE a nivel de sistema, se pueden emplear dos tipos de técnicas para evaluar cada punto de diseño: evaluación basada en la simulación y estimación basada en enfoques analíticos. Evaluación basada en simulación Las simulaciones son muy apropiadas para analizar los comportamientos dinámicos y esporádicos que ocurren en el sistema. Un claro ejemplo es el efecto de la contención, el cual suele producirse si varios PEs del sistema compiten simultáneamente por hacerse con el uso de un mismo recurso compartido. Esta cualidad es lo que precisamente permite que las evaluaciones basadas en simulaciones puedan revelar resultados más realistas con respecto a los obtenidos en las estimaciones analíticas. Estimación basada en enfoques analíticos Los métodos de estimación analítica son idóneos para aquellos casos en los que el sistema presente un comportamiento determinista, o que WCET es una suposición razonable para el sistema objeto de evaluación. A diferencia de la evaluación basada en CHAPTER 6 133 simulación, los modelos analíticos se caracterizan por un tiempo de ejecución corta. Sin embargo, el principal inconveniente de este enfoque sigue siendo la falta de precisión en la evaluación. Una revisión de los métodos de estimación analítica se puede encontrar en el capítulo 4 de esta tesis. 6.1.2.2.3 El generador de la descripción del sistema Independientemente de la naturaleza de las técnicas de evaluación (es decir, utilizar la simulación o estimación analítica), en primer lugar se debe crear un modelo de sistema para evaluarlo adecuadamente. En particular, este último se convierte en un requisito cuasi-indispensable si las evaluaciones se basan en la simulación. En estos casos, para realizar la simulación y obtener información del sistema (entre las que se incluyen las medidas o métricas), las herramientas de simulación suelen requerir un archivo ejecutable del modelo de sistema (ESM), que puede considerarse como un modelo virtual o meta-modelo del sistema. Dicho modelo virtual no sólo debe incluir información acerca de la funcionalidad de la aplicación y de los detalles de la arquitectura, sino especificar también cómo ambos dominios se fusionan. En este punto, cabe hacer hincapié en que el principio del Y-Chart facilita en gran medida la concepción y creación de estos ESM. De acuerdo con este principio, un sistema (y en nuestro caso, un ESM) se puede especificar mediante la combinación de tres modelos: un modelo de la aplicación, un modelo de la arquitectura y un modelo de mapeo. Esto último significa que el principio de Y-Chart separa explícitamente el modelado de la aplicación y el de la arquitectura. El modelo de la aplicación describe el comportamiento funcional de la aplicación utilizando, por ejemplo, redes de procesos de Kahn (KPN) o grafos de tareas. Al mismo tiempo, un modelo de la arquitectura especifica el diseño arquitectural (por medio de los componentes predefinidos y altamente configurables proporcionados por la biblioteca de las herramientas) y captura sus rendimientos o prestaciones. Por último, otro fichero describe cómo se mapea el modelo de la aplicación en el modelo de la arquitectura para su co-simulación con el fin de obtener métricas del sistema en análisis posteriores. Comparado con otras propuestas tradicionales (como FPGA o simulaciones RTL), un ESM que se crea siguiendo el principio de Y-Chart presenta varias ventajas: • El diseñador puede disponer del ESM en una fase muy temprana del proceso de diseño. Esta es una consecuencia implícita de trabajar a un nivel de abstracción RESUMEN EN ESPAÑOL 140 hardware. Por lo tanto, CASSE debe permitir al diseñador modelar estos aspectos de la aplicación de un modo abstracto. Por otra parte, para realizar DSE de una forma eficiente, la aplicación debe modelarse de forma independiente de la arquitectura. Esto significa que dichos modelos deben construirse de forma ortogonal, y fusionarse explícitamente en un paso de mapeo aparte. • Una librería de componentes genéricos y altamente configurable. Con el fin crear rápidamente diferentes modelos arquitecturales, y explorar así un gran espacio de diseño, CASSE debe proporcionar un conjunto de modelos de los recursos arquitecturales en su librería de trabajo de forma que el esfuerzo de crear nuevos modelos de arquitectura y derivar modelos de los existentes resulte mínimo. Los componentes de esta librería deben ser lo suficientemente genéricos y configurables, para permitir emular las funciones de un amplio repertorio de componentes arquitecturales. Finalmente, estos modelos de componentes también tienen que ser capaz de dar soporte al mapeo de la funcionalidad de la aplicación en ellos. • Análisis avanzado del rendimiento. En las simulaciones a nivel de sistema, el diseñador debe analizar una gran cantidad de información y resultados acerca del funcionamiento del sistema antes de decidir si un punto de diseño cumple o no con los requisitos establecidos. Interpretar tal cantidad de información con el fin de encontrar los cuellos de botella y posibles vías de optimización no es una tarea trivial en el diseño de los SoCs modernos. Por lo tanto, CASSE debe proporcionar los mecanismos necesarios que faciliten la identificación de los puntos conflictivos dentro de cualquier diseño. • Facilidad para crear/configurar los modelos, rápida simulación del sistema y una buena precisión en las evaluaciones. Como se comentó con anterioridad, para simular cada punto de diseño, el diseñador debe crear y configurar previamente el ESM correspondiente a dicho punto de diseño. Obviamente, cuanto más rápido se lleve acabo este proceso, mayor cantidad de alternativas de diseño pueden explorarse. Para conseguir este objetivo, CASSE debe cumplir con los siguientes requisitos: 1) CASSE debe proporcionar una interfaz fácil de usar para usuario. Además, dicha interfaz debe poseer cierta capacidad de scripting con el objetivo de automatizar y acelerar las modificaciones en el ESM. CHAPTER 6 141 2) Para explorar grandes espacios de diseño, es preciso que cada simulación sea llevada acabo lo más rápidamente posible. En estos términos, CASSE debe proporcionar al menos un factor de mejora de x1000 con respecto a las simulaciones RTL si se desea obtener una mejora significativa en la DSE a nivel de sistema. Esto nos lleva a la velocidad de la simulación en el orden de los Mhz. 3) Obviamente, siempre es preferible para un diseñador trabajar con la mayor precisión posible. No obstante, a menudo trabajar con un cierto nivel de precisión puede ser suficiente para mejorar la eficiencia de la DSE y reducir los esfuerzos de crear el ESM. En este contexto, el fin último de las herramientas de simulación a nivel de sistema es evaluar rápidamente el mayor número posible de alternativas y proporcionar al diseñador la información necesaria que le ayude a decidir, por ejemplo, si un sistema es mejor o peor que otro en determinados aspectos. 6.2.3.1 Metodología de diseño de CASSE Ya hemos comentado a lo largo de este documento la importancia de la herramienta de simulación en el proceso de diseño, porque en cierto modo, ésta limita las capacidades de actuación del diseñador y también es la que condiciona el flujo de diseño que debe utilizar. En esta tesis, nos hemos apoyado en CASSE, una herramienta CAD que permite cubrir las tareas del modelado de la aplicación, modelado arquitectural, mapeo, simulación, análisis y optimización progresiva bajo un único entorno de trabajo. Una característica esencial de CASSE es que se maneja a través de interfaces basadas en ficheros de texto, es decir, no tiene una interfaz gráfica propiamente dicha que interactúa con el diseñador. Estos ficheros son utilizados por la herramienta durante la simulación para crear y configurar el modelo de la aplicación, el modelo de la arquitectura y el modelo del mapeo. Una vez compilado el conjunto de todos estos ficheros, la herramienta devuelve como resultado un ESM. No obstante, en las modificaciones sucesivas sobre los parámetros arquitecturales del sistema (no sobre el código de la aplicación), el diseñador sólo necesita retocar estos valores dentro del fichero correspondiente, evitándose así recompilar todo nuevamente. Este detalle permite realizar de forma totalmente automatizada exploraciones de numerosas combinaciones de parámetros del sistema, lo que supone un importante ahorro de tiempo. RESUMEN EN ESPAÑOL 142 El esquema del flujo de diseño de la herramienta se muestra en la Fig. 2.1. A continuación explicaremos muy brevemente las funciones de cada etapa que constituye este flujo de diseño. Modelado de la aplicación. En primer lugar, el código de una aplicación se descompone en forma de grafo de tareas. Para CASSE, las tareas son entidades que ejecutan paralelamente sus procesos entre sí y se comunican a través de canales unidireccionales. Dos tareas conexas se comunican y se sincronizan a nivel TTL mediante las llamadas a las primitivas de sus puertos, consiguiendo de esta forma una separación explícita entre la computación y la comunicación. También hay que hacer hincapié en que la funcionalidad de las tareas está fijada en el momento de compilación, y que a diferencia de los parámetros arquitecturales del sistema, éstos últimos pueden modificarse sin necesidad de recompilar todos los modelos, como se verá más adelante. Finalmente, cabe mencionarse que la paralelización de la aplicación en el grafo de tarea es un proceso manual, el cual depende en gran medida de las experiencias y conocimientos del diseñador sobre la aplicación en cuestión. Básicamente, el diseñador debe decidir dónde insertar los puntos de ruptura en el código fuente e introducir los puertos y los canales en dichos puntos. La automatización de este proceso de paralelización no es objeto de esta tesis, aunque puede considerarse como una posible línea de trabajo de cara al futuro. Modelado de la arquitectura. Una plantilla de arquitectura consta típicamente de unos elementos de procesamiento, elementos de almacenamiento, elementos de comunicación, y dispositivos de I/O. Las plantillas o modelos de estos recursos arquitecturales están disponibles en la librería de la herramienta de CASSE, por lo que el diseñador sólo tiene que seleccionarlos y configurarlos para crear el modelo de sistema deseado. Esta manera modular de construir sistemas facilita la expansión, reconfiguración, y la reutilización de la plantilla, aportando así importantes ventajas en cuanto al tiempo y esfuerzo en el proceso de diseño. Mapeo. Una de las principales ventajas de la herramienta es su flexibilidad a la hora mapear la funcionalidad de la aplicación en el modelo de la arquitectura. Es decir, CASSE soporta el mapeo directo de las aplicaciones TTL (es decir, tareas y canales) en los componentes arquitecturales y también la ejecución del sistema resultante sin necesidad de cambios en el código fuente (es decir, el código fuente original de las tareas se ejecuta directamente en el modelo de la arquitectura). Esta técnica se llama CHAPTER 6 143 emulación del código fuente (HCE), el cual evita el uso de modelos de hardware y Simuladores de Juegos de Instrucciones (ISS). Por tanto, reduce el esfuerzo del modelado y permite a su vez simulaciones más rápidas. Por otro lado, las informaciones de tiempo que refleja el coste de cómputo (de la funcionalidad en un PE) aún deben anotarse en las tareas. Esto último puede realizarse de modo automático o puede anotarse de forma manual en cada tarea. Sin embargo, esta flexibilidad para el mapeo también representa un hándicap para los diseñadores. Es decir, si bien la versión actual de CASSE permite mapear manualmente (y selectivamente) cualquier aplicación en una plantilla arquitectural, CASSE no proporciona ninguna estrategia o técnica que permita que dicho proceso se realice de forma automática. Este proceso puede suponer unos esfuerzos considerables para el diseñador, sobre todo cuando la aplicación en cuestión tiene una complejidad considerable. Simulación. Como ya se comentó con anterioridad, cada una de las posibles combinaciones de las opciones de diseño equivale a un punto de diseño en el espacio de diseño. Obviamente, cuando más puntos haya, mayor será el espacio a explorar y consecuentemente, más compleja será la labor de análisis del diseñador. Por tanto, la etapa de simulación tiene como misión principal la de proporcionar la información necesaria relativa al punto de diseño analizado, de modo que el diseñador pueda analizarla con posterioridad. Sin embargo, a pesar de las numerosas métricas capaces de ser capturadas por CASSE (tales como el número de bytes transmitidos, los ciclos de ocupación/ocio de un PE, los ciclos de retardo, etc.), otros indicadores tan importantes como la potencia y coste/área no están siendo considerados en la versión actual de CASSE. Este punto de flaqueza de CASSE limita en gran medida los tipos de problemas de optimización que el diseñador puede tratar. Por esto entendemos que ésta puede ser una posible línea de investigación futura con el fin de mejorar las prestaciones de CASSE. Análisis y optimización. El análisis de los resultados de las simulaciones ayuda a entender las propiedades cualitativas y cuantitativas del sistema en una fase temprana del proceso del desarrollo del producto. De este análisis se pueden extraer conclusiones relativas a diferentes opciones de diseño y su impacto en el funcionamiento del sistema. Finalmente, la eficiencia y la viabilidad de la implementación final dependerán también de estos trabajos de evaluación y optimización. RESUMEN EN ESPAÑOL 144 6.2.3.2 La estructura interna de CASSE Como se puede ver en Fig. 2.7, CASSE está estructurada en tres niveles o capas. • Capa de interfaz con el usuario. Esta capa funciona como la interfaz del usuario para controlar la herramienta. Como se mencionó con anterioridad, existen varios grupos de ficheros/modelos de descripción que permiten a los diseñadores controlar plenamente la creación y la configuración de cada ESM: el fichero del grafo de tareas (o aplicación), el fichero de la arquitectura y el fichero del mapeo. • Capa del núcleo de la herramienta. Esta capa implementa la funcionalidad básica de la herramienta. Aparte de contener un programa de análisis que lee e interpreta los modelos de descripción (especificado por los diseñadores), esta capa también lleva incorporada dos librerías específicas: la biblioteca de aplicaciones (APP) y la librería de componentes arquitecturales (ARCH). Por otra parte, CASSE es capaz de llevar a cabo dos tipos de simulaciones: simulaciones funcionales y simulaciones de rendimiento. Mientras que las simulaciones funcionales sólo requieren el modelo de grafo de tareas, CASSE necesita leer y analizar todos los modelos para realizar las simulaciones de rendimiento. El resultado de este proceso es un ESM, es decir, un archivo ejecutable del modelo que describe el sistema en su conjunto. • Capa del núcleo del simulador. Estos ESMs se ejecutan con el núcleo de SystemC, que constituye la tercera capa de la herramienta. Durante las simulaciones, los resultados y las estadísticas son monitorizados y guardados en los archivos de salida para su análisis posterior. 6.2.4 Caso de estudio: sistema de seguimiento visual En esta sección, presentamos un conjunto de experimentos de DSE con el fin de demostrar las capacidades y el funcionamiento de CASSE. Asimismo, presentamos también la aplicación de referencia que hemos utilizado en todos los experimentos de DSE de esta tesis. 6.2.4.1 Algoritmo de seguimiento visual La aplicación de referencia que hemos utilizado en este caso es un algoritmo de seguimiento visual basado en la técnica de correlación, el cual ha sido desarrollado por los investigadores del Instituto Universitario de Sistemas Inteligentes Autónomos y CHAPTER 6 145 Aplicaciones Numéricas en Ingeniería del ULPGC. A modo de resumen, resaltar que el algoritmo realiza un proceso de correlación de la imagen entrante con un patrón de referencia que el criterio de ajuste utilizado en dicho proceso es el conocido como la suma de la diferencia absoluto (SAD), como se recoge en la expresión (2.1). El resultado Sij que se recoge en la expresión (2.1) representa un valor de la distorsión, de modo que cuanto menor sea dicho valor mayor será la correlación entre la imagen y el patrón utilizado. Por otro lado, el valor mínimo de la distorsión es el utilizado para determinar el umbral de discriminación o actualización del patrón de referencia. Dicho en otras palabras, sólo se reemplazará o actualizará el patrón si existe una gran probabilidad de perder el objetivo, lo cual viene marcado por el valor de la mínima distorsión de la imagen actual con respecto al umbral de actualización. Utilizando este sistema de actualización dinámica del patrón de referencia, se reduce de forma considerable el número de operaciones de correlación innecesario y también, el número de accesos a las memorias. En consonancia con las explicaciones del apartado de la metodología de diseño de CASSE, el algoritmo de la aplicación en cuestión es estructurado en primer lugar como un grafo de tareas. El requisito de tiempo real de la aplicación exige procesar 25 imágenes/s, donde el tamaño de las imágenes y el del patrón de referencia, son 320x240 y 24x24 píxeles, respectivamente. Finalmente, queremos hacer hincapié en que la importancia de este grafo está en que, por un lado, permite al diseñador identificar claramente el orden y la dependencia de las tareas y por otro lado, también revela la estructura de datos implicada en cada transacción. Es decir, una vez separados los puntos de comunicación, el diseñador puede tener una visión más completa de las fuentes y destinos de cada dato, lo que facilita en gran medida el mapeo de estos canales de comunicación a la memoria más adecuada. Paralelamente al desarrollo del algoritmo de seguimiento, se ha modelado una plantilla de arquitectura, la cual no tiene carácter ad-hoc sino que es genérica, ya que se ha construido sin tener en cuenta las peculiaridades de las tareas y su interrelación, esto es se ha elegido de forma totalmente independiente de la aplicación. En la práctica, existen muchas implementaciones arquitecturales capaces de satisfacer los requisitos demandados por una aplicación dada. Obviamente, cada alternativa tendrá su pros y su contras. No obstante, nuestro objetivo en este capítulo no consiste en realizar un análisis comparativo de distintas alternativas, sino más bien centrarnos en la exploración del espacio de diseño de una plataforma arquitectural en concreto. RESUMEN EN ESPAÑOL 146 En el caso de este estudio, hemos propuesto una arquitectura muy genérica, que se basa en un procesador RISC programable, unos buses, diversas memorias compartidas y diversos módulos hardware que bien podrían actuar de aceleradores, DSP, ASIC o coprocesadores. También se han incorporado al sistema unos puentes que acomodan la comunicación entre los buses y, a su vez, adaptar los diferentes dominios de reloj. Todos los elementos se pueden encontrar en la librería de trabajo de CASSE, de modo que el trabajo del diseñador se limitará a organizarlos y configurarlos de la forma apropiada. Por ejemplo, un procesador RISC ARM-9 se puede obtener fácilmente configurando los parámetros de un PE: la política de planificación, el tiempo de cambio de contexto, el ciclo de lectura/escritura, y otros parámetros. Mientras que, por ejemplo, configurando adecuadamente la política de arbitraje y el tamaño de los búferes de I/O de un NE, se puede modelar un AMBA bus. 6.2.4.2 Resultados basado en una solución monoprocesador Antes de comenzar con el proceso del mapeo, se ha compilado el código del algoritmo en ADS (ARM Developer Suite) versión 1.2, para un procesador de referencia, ARM922 a 200 Mhz. El código ensamblador devuelto por esta herramienta nos permite identificar un perfil de tiempo de ejecución para cada tarea del grafo. Esta información se muestra en Fig. 2.9 y en ella se puede observar que esta versión del estudio del sistema con un único procesador está muy lejos de conseguir el comportamiento de tiempo real. 6.2.4.3 Resultados basado en un SoC multiprocesador Para cumplir con la restricción de tiempo real, se ha considerado una solución basada en múltiples PEs, es decir, en vez de empotrar todo el SW en un único procesador, se distribuirán las tareas entre varios PEs, aprovechando de esta forma el procesamiento en paralelo. Inicialmente, se utilizaron solamente tres PEs (PE 1, PE 2 y PE 4). Si tenemos en cuenta la información obtenida en ADS, vemos que la tarea SAD es muy costosa desde el punto de vista de cómputo. Además, dado que está muy acoplada a la tarea de búsqueda de mínimos, se ha decidido asignar ambas tareas en el mismo PE. Por otro lado, en cualquier sistema, un procesador de vídeo puede realizar más eficientemente la tarea de recepción y de conversión de formato que un procesador RISC, y por ello, estas tareas del grafo se mapearán en el PE 4, por ejemplo. Finalmente, las tareas restantes se agrupan en el PE 1 y las canales de comunicación se mapean en la memoria compartida. CHAPTER 6 147 En este caso, hemos realizado una exploración del espacio de diseño manteniendo la arquitectura del bus, el tipo y número de memorias, y la configuración del sistema, pero variando la frecuencia (o reloj) y el factor de aceleración de los coprocesadores. Y los resultados obtenidos se muestran en Fig. 2.11. En ella se puede observar, por ejemplo, que para un rango de frecuencias comprendido entre 200 y 800 Mhz, y unos factores de aceleración desde x1 hasta x10, el sistema es capaz de procesar 25 imágenes/s si se trabaja a 400 Mhz y el coprocesador tiene un factor de x10. Con otras combinaciones, sin embargo, difícilmente se puede procesar 25 imágenes en cada segundo. Evidentemente, muchos puntos de diseño son capaces de lograr la restricción de tiempo real requerida, aunque muchas veces no todos ellos son deseables desde el punto de vista de implementación física. Por ello, se ha utilizado adicionalmente el criterio de mínima carga de bus en el sistema para elegir la solución óptima de entre todas las factibles. Este criterio tiene su razón de ser en el siguiente argumento: cuanto menos tiempo utiliza un PE el bus compartido, más PEs podrán tener acceso al mismo y por consiguiente, más tareas y/o aplicaciones pueden ejecutarse simultáneamente en el sistema. En este caso, al conocer de antemano perfectamente el volumen de datos implicado en el sistema, la solución de mínima carga en el bus se traduce automáticamente en la solución de mínima carga de sincronización. Consecuentemente, la solución inicial es aquella dada por la combinación de 400 Mhz y un factor de aceleración x10. En este punto conviene explicar que la carga total del bus está compuesta de, por un lado, los datos procedentes de las operaciones de lectura y escritura y, por otro lado, de la información de sincronización que envían los PEs a las memorias compartidas vía bus, convirtiéndose de esta forma en un cuello de botella para el sistema. Este detalle es particularmente interesante cuando tenemos PEs con reparto no equilibrado de cargas de computación. Dicho con otras palabras, cuando un procesador necesita un dato de la memoria, primero testea la memoria para asegurar la presencia del dato: si el dato está disponible, lo consume; si no, el procesador puede optar por realizar otras operaciones o por continuar testeando la memoria. Este último caso es comúnmente conocido con el nombre de la sobre-sincronización, que es causa de un elevado volumen de tráfico innecesario en el bus, penalizando el rendimiento del sistema. La Fig. 2.12 muestra las diferentes cargas de sincronización producidas por cada puerto de las tareas asociadas a cada PE. Si existe una distribución equilibrada de la carga de trabajo, circulará una cantidad mínima de tráfico de RESUMEN EN ESPAÑOL 148 sincronización por el sistema, siendo este caso representado como el ideal. En cambio, en el caso de nuestra solución, vemos perfectamente cómo determinados puertos acusan precisamente de este problema de sobre-sincronización. Una solución para paliar el efecto de la sobre-sincronización es reubicar los canales accedidos por los puertos afectados por dicho fenómeno. En este caso, hablamos del puerto 2 del PE1 y del puerto 1 del PE 4. Por tanto, los canales asociados a dichos puertos se mapean nuevamente en unas memorias locales y, de este modo, dichos puertos evitan acceder al bus principal para disponer del dato de la memoria principal del sistema, disminuyendo considerablemente la carga del bus con estas dos medidas. Finalmente, queremos hacer hincapié en que todos estos mapeos se han realizado de forma manual, es decir, en función de los resultados obtenidos en cada simulación, modificamos el fichero del mapeo o creamos manualmente el nuevo modelo de mapeo correspondiente. 6.2.4.4 Análisis en un entorno multi-aplicación Siguiendo con nuestro propósito de construir un CVS más complejo, otro objetivo prioritario en nuestro análisis es estudiar la posibilidad de mapear más de una aplicación en el sistema, manteniendo los comportamientos de tiempo real del sistema de seguimiento. Para ello, hemos modelado otra aplicación productor-consumidor con las características típicas de las aplicaciones de procesado de imágenes, en donde los flujos de datos son regularmente o periódicamente recibidos y procesados. Aquí lo que nos interesa es analizar el efecto del tráfico generado por esta aplicación en el sistema inicial y no tanto el procesado que realiza esta nueva aplicación. Con este planteamiento en mente, hemos desarrollado una nueva aplicación para que genere cuatro tipos diferentes de tráfico: - tráfico constante, donde los datos de ambas aplicaciones compiten por la misma memoria; - tráfico periódico, es decir, donde la nueva aplicación accede a los recursos del sistema a una tasa específica, siendo la misma 10 ms y 20 ms; y - finalmente, un tráfico aleatorio. Las tareas de la nueva aplicación (productor-consumidor) y sus canales se mapean en la memoria compartida principal. Tras numerosos experimentos y simulaciones, obtuvimos CHAPTER 6 149 los resultados que se muestran en Fig. 2.14. En ella se puede observar que el rendimiento de nuestra solución anterior (es decir, para una configuración de 400 Mhz y un factor de aceleración de x10) se mantiene intacta si la nueva aplicación produce un tráfico constante con un tamaño de los paquetes inferior a 100 Kbytes, u otra que produce un trafico con periodicidad de 10 ms, siendo el tamaño de sus datos menor a 2 Mbytes. 6.2.5 Conclusiones En este capítulo hemos presentado a CASSE, una herramienta de modelado y simulación a nivel de sistema basada en SystemC. Hemos explicado los aspectos claves para entender el funcionamiento de CASSE y también hemos presentado un conjunto de experimentos de DSE para demostrar las capacidades de esta herramienta CAD. Los resultados obtenidos indican que CASSE es una herramienta potente que posee muchas cualidades para llevar a cabo de forma eficiente diferentes tipos de experimentos de DSE. Sin embargo, quedan todavía mucho trabajo por hacer para que todo el proceso de modelado y creación de ESM puede realizarse de una forma automatizada. Con esta idea en mente, los capítulos 3 y 4 se centrarán en proporcionar los mecanismos para reducir el esfuerzo del diseñador en el modelado/creación de cada ESM y también hacer más eficiente el proceso de la DSE a nivel de sistema.