This paper presents SHAPES, a tool for hardwaresoftware partitioning. It is based on two main paradigms: the implementation of the partitioning tool by means of an expert system, and the use of fuzzy logic to model the parameters involved in the process. 1

A Knowledge-based System for Hardware-Software Partitioning z Dep. Ing. Electr nica o ETSIT, Univ. Polit cnica Madrid e E 28040 Madrid, Spain fmarisa,lopezg@die.upm.es

M. L. L pezz, C.A. Iglesiasy and J. C. L pezz o o fcif@tel.uva.esg

Dep. TSC e Ing. Telem tica a ETSIT, Univ. de Valladolid E 47011 Valladolid, Spain

This paper presents SHAPES, a tool for hardwaresoftware partitioning. It is based on two main paradigms: the implementation of the partitioning tool by means of an expert system, and the use of fuzzy logic to model the parameters involved in the process.

Abstract

acquired in manual partitioning, in the form of if-then rules. Since this knowledge is imprecise in nature, we use fuzzy logic 5 to model the variables of the rules.

3 Partitioning Model

1 Introduction

Hardware-software partitioning deals with the assignment of parts of a system description to heterogeneous implementation units: ASICs, standard or embedded processors, memories, etc. This is a key task in HW-SW co-design, because the decisions that are made at this time impact directly on the performance and cost of the nal implementation. To achieve such a di cult labor, complex algorithms have been developed in di erent co-design environments 2, 1, 3, 4 . In this paper arti cial intelligent techniques are proposed for the partition of complex systems. SHAPESSoftware-HArdware Partitioning Expert System is a fuzzy expert system which provides an easy way to address HW-SW partitioning. This tool considers two important aspects of general optimization problems: the possibility of dealing with imprecise and uncertain valuesby means of the de nition of fuzzy magnitudes, and the use of the expertise of the system designer in the decision making process.

The input to the partitioning process is an execution ow graph which comes from the initial system speci cation. In this graphdirected and acyclic, nodes stand for tasks and edges represent data and control dependenciescoarse granularity. Every graph node i is labeled with additional information: hardware areahai, hardware execution timehti, software execution timesti and the average number of times the task is executedni. Edges have also associated a communication valuecommij obtained from: the transfer timettrans, the synchronization timetsynch and the average number of times the communication takes place nij . The target architecture considered consists of one processor running the software, one ASIC and a shared memory accessed through a common bus. The output of the partitioning tool is not only an assignment of blocks, but also their scheduling and the communication values produced in the interface. i;j i;j

4 SHAPES Architecture 4.1 Classi cation Module

2 Rationale for Hw-Sw Partitioning using a Fuzzy Expert System

In the traditional design style, heterogeneous system development was fully characterized by an initial partitioning phase performed manually by the system de

signer. It was based on di erent pieces of estimation and basically the designer knowledge. To automate this partitioning phase, it is necessary to mimic the way a skilled designer performs this step. We propose a di erent approach based on expert systems technology, that uses the designers' knowledge  This work has been funded by projects HADACICYT TIC97-09 28 and BELSIGNHCM CHRX-CT94-0459 y This research was done while the author was visiting the Dep. Ing. Sistemas Telem ticosUniv. Polit. Madrid. a

The architecture of SHAPES is described in gure 1. This block diagram describes the design ow followed by the expert system, whose modules will be explained in the following sections. The rst step in SHAPES is to determine which blocks of the initial speci cation are more suited to be implemented in special purpose hardware or as software running on a standard processor. This step is performed by a rule based classi er module. The crisp output of the classi er module is the set of input tasks ordered by their implementation degree: value 0 stands for hardware and 1 for software. If no rule is activated for a given input task, the implementation degree is unknown0.5. Furthermore, in that case, the tool can be con gured to ask the designer an