A Hardware-Software Co-Design System for

Embedded Real-Time Applications

Sérgio Vanderlei Cavalcante

A thesis submitted for the degree of Doctor of Philosophy

in the
Department of Electrical and Electronic Engineering
at the
University of Newcastle upon Tyne

June, 1997
 S.V. Cavalcante
___________________________________________
S.V. Cavalcante 
___________________________________________

!"342!#4

This dissertation presents an environment for the co-design of hardware and software in
critical real-time embedded systems. The environment is targeted to producing solutions
suitable for multi-processor architectures. The challenges and difficulties faced in
developing such an environment are shown.

The system includes three major parts:

• A specification tool which uses hierarchical high-level timed Petri nets, while
enforcing a design methodology to ensure consistent specifications;

• A scheduling algorithm able to schedule a set of processes with deadlines, release

times, precedence, exclusion relations, and which allows process pre-emption, in a
heterogeneous multi-processing architecture;

• An analysis and partitioning algorithm that has real-time constraints as its primary
concern.

At the end of the dissertation some examples are presented to illustrate the use of
the system.
 S.V. Cavalcante
___________________________________________
S.V. Cavalcante 
___________________________________________

4ABLE OF #ONTENTS Page

!BSTRACT  

,IST OF )LLUSTRATIONS   

,IST OF 4ABLES      

!CKNOWLEDGEMENTS   

 )NTRODUCTION  

1.1 Embedded Systems and Co-Design......................................................................... 18

1.2 Objectives of This Dissertation ............................................................................... 20
1.3 Proposed Method..................................................................................................... 20
1.4 Organisation of the Dissertation.............................................................................. 21

 2ELATED 7ORK 

2.1 Hardware-Software Co-Design ............................................................................... 23

2.1.1 Co-Specification ............................................................................................. 24
2.1.2 Partitioning ..................................................................................................... 25
2.1.3 Hardware-software Co-Synthesis................................................................... 25
2.1.4 Analysis .......................................................................................................... 26
2.1.5 Co-simulation and Prototyping....................................................................... 26
2.2 Existing Co-design Approaches .............................................................................. 28
2.2.1 Stanford University......................................................................................... 28
2.2.2 COSYMA (Ernst and Henkel )....................................................................... 30
2.2.3 Barros et al...................................................................................................... 31
2.2.4 Oxford Hardware Compilation Group - Oxford University........................... 32
2.2.5 Eles et al. ........................................................................................................ 33
2.2.6 CFSM ............................................................................................................. 35
2.2.7 Princeton University....................................................................................... 36
2.2.8 TASSIM ......................................................................................................... 37
2.2.9 Chinook .......................................................................................................... 38
2.3 Co-design Taxonomy .............................................................................................. 39
 S.V. Cavalcante
___________________________________________

2.4 Real-Time Systems ..................................................................................................41

2.4.1 Process Characterisation .................................................................................42
2.4.2 Scheduling Methodologies..............................................................................43
2.4.3 Scheduling in This Dissertation ......................................................................44
2.5 Petri Nets..................................................................................................................45
[Link] High-Level Petri Nets ............................................................................46
[Link] Time Modelling in Petri Nets.................................................................47
2.5.2 Petri Nets in This Dissertation ........................................................................47
2.6 Summary ..................................................................................................................47

 #O $ESIGN -ETHODOLOGY  

3.1 Co-Design System Overview...................................................................................49

3.1.1 Design Process ................................................................................................50
3.2 Design Specification ................................................................................................51
3.3 System Modelling ....................................................................................................52
3.3.1 Basic Net .........................................................................................................53
[Link] Architecture Specification......................................................................53
3.3.2 Timing Specification.......................................................................................53
3.3.3 Process Nets ....................................................................................................54
[Link] Periodic Transitions: ..............................................................................55
[Link] Input and Output Places: ........................................................................55
[Link] Mutual Exclusion: ..................................................................................55
3.3.4 Hierarchy.........................................................................................................56
[Link] Super-Transitions ...................................................................................57
[Link] Stores:.....................................................................................................59
3.3.5 Design Consistency.........................................................................................60
[Link] Sporadic Tasks Transformation .............................................................62
3.4 Time Wizard ............................................................................................................62
3.4.1 Design Flow ....................................................................................................63
[Link] Processors Definition .............................................................................64
[Link] Design Specification ..............................................................................64
[Link] System Profiling and Simulation ...........................................................67
[Link] Consistency and Refinements ................................................................68
S.V. Cavalcante 
___________________________________________

3.4.2 Additional Features: Intra-Task Assessment.................................................. 70

3.5 Summary.................................................................................................................. 73

 4ASK 3CHEDULING  

4.1 Problem Complexity................................................................................................ 75

4.2 Algorithm Overview................................................................................................ 76
4.3 Problem Transformation.......................................................................................... 77
4.4 Segment Basic Schedule.......................................................................................... 78
4.4.1 Timing Relation Adjustments ........................................................................ 79
4.4.2 Consistency Check ......................................................................................... 81
4.4.3 Segment Eligibility......................................................................................... 82
4.4.4 Basic Schedule................................................................................................ 83
4.5 Basic Schedule Improvement .................................................................................. 85
4.5.1 Uni-processor Schedule Improvement ........................................................... 86
4.5.2 Multi-processor Schedule Improvement ........................................................ 87
4.6 Branch-And-Bound Algorithm................................................................................ 90
4.6.1 Node Pruning.................................................................................................. 90
4.6.2 Calculating ,,"N ......................................................................................... 91
[Link] LLB1(N) ................................................................................................. 92
[Link] LLB2(N) ................................................................................................. 92
4.6.3 Branch-and-Bound Implementation ............................................................... 94
4.6.4 Context Switching Considerations ................................................................. 95
4.7 Examples ................................................................................................................. 95
4.8 Summary.................................................................................................................. 97

 (ARDWARE 3OFTWARE 0ARTITIONING  

5.1 Algorithm Overview................................................................................................ 99

5.2 Pre-Partitioning...................................................................................................... 101
5.2.1 Consistency-Based Partitioning.................................................................... 103
5.2.2 Partitioning Lists Creation............................................................................ 103
[Link] Precedence-Based Partitioning Lists ................................................... 104
[Link] Exclusion-Based Partitioning Lists ..................................................... 105
5.3 System Partitioning ............................................................................................... 107
 S.V. Cavalcante
___________________________________________

5.4 Cost Function .........................................................................................................109

5.5 Moving tasks to hardware ......................................................................................111
5.6 Possible Results .....................................................................................................111
5.7 Example .................................................................................................................113
5.8 Summary ................................................................................................................115

 %XAMPLES  

6.1 Mine Pump Controller ...........................................................................................118

6.1.1 Initial Specification .......................................................................................118
6.1.2 Model Refinement.........................................................................................120
6.1.3 Results...........................................................................................................121
6.2 Motor Controller ....................................................................................................122
6.2.1 Formulation...................................................................................................122
6.2.2 Temporal Requirements................................................................................123
6.2.3 System Specification.....................................................................................123
6.2.4 Partitioning....................................................................................................126
6.2.5 Operation Scheduling....................................................................................126
[Link] Operation-Level Scheduling Results....................................................127
6.3 York1 .....................................................................................................................128
6.3.1 Partitioning Summary ...................................................................................131
6.4 York2 .....................................................................................................................131
6.4.1 Scheduling Results........................................................................................132
6.5 Summary ................................................................................................................132

 #ONCLUSIONS AND &UTURE 7ORK  

7.1 Objectives...............................................................................................................135
7.2 Summary of The Dissertation ................................................................................136
7.2.1 Specification Method ....................................................................................137
7.2.2 Scheduling Algorithm ...................................................................................138
7.2.3 Partitioning Algorithm ..................................................................................140
7.3 Future Work ...........................................................................................................141
7.3.1 Resource Utilisation and FPGAs ..................................................................141
7.3.2 Stochastic Analysis .......................................................................................142
S.V. Cavalcante 
___________________________________________

7.3.3 Framework Expansion.................................................................................. 142

!PPENDIX ! #ABERNET AND 4%2 .ETS  

A.1 Tracing Tool ......................................................................................................... 146

!PPENDIX " 0ETRI .ET %XTENSION 3EMANTICS  

!PPENDIX # 4HEOREMS  

!PPENDIX $ 0ARTITIONING 2EPORT 

2EFERENCES  

 S.V. Cavalcante
___________________________________________

,IST OF )LLUSTRATIONS

Figure 1.1. World-wide revenues for micro-controllers and DSP sales [35].......................19
Figure 1.2. Basic co-design architecture..............................................................................19
Figure 2.1. Basic co-design approach ..................................................................................24
Figure 2.2. CODES Environment ........................................................................................27
Figure 2.3. Vulcan co-synthesis system [34] .......................................................................29
Figure 2.4. Multi-clustering partitioning and implementation [8] .......................................31
Figure 2.5. The HARP Reconfigurable Computer Module [97]..........................................33
Figure 2.6. Module Partitioning...........................................................................................37
Figure 2.7. The Chinook System..........................................................................................39
Figure 2.8. Petri Nets ...........................................................................................................45
Figure 3.1. Proposed co-design environment.......................................................................51
Figure 3.2. Graphical representations of the Petri Net extensions.......................................52
Figure 3.3. Process nets........................................................................................................54
Figure 3.4. Mutual exclusion representation........................................................................56
Figure 3.5. CP-nets hierarchy...............................................................................................57
Figure 3.6. Hierarchical modelling: a super-transition and its subnet .................................58
Figure 3.7. Using stores for subnet communication ............................................................60
Figure 3.8. Periodic-sporadic communication consistency..................................................61
Figure 3.9. Subnets consistency and transformation............................................................61
Figure 3.10. Dual triggering inconsistency..........................................................................62
Figure 3.11. Class definitions ..............................................................................................64
Figure 3.12. Processors definition........................................................................................64
Figure 3.13. Time Wizard main window showing an initial stage design...........................65
Figure 3.14. Transition attributes window ...........................................................................66
Figure 3.15. Super-transition attributes window..................................................................67
Figure 3.16. Flattened specification.....................................................................................68
Figure 3.17. Consistent specification...................................................................................69
Figure 3.18. Path tracing analysis ........................................................................................71
Figure 3.19. Conditional tracing analysis.............................................................................71
Figure 3.20. Firing Correlation Analysis .............................................................................72
Figure 3.21. Loop iteration analysis.....................................................................................72
S.V. Cavalcante 
___________________________________________

Figure 4.1. Timing constraints adjustments ........................................................................ 81

Figure 4.2. Scheduling gap.................................................................................................. 88
Figure 4.3. Narrowing the gap............................................................................................. 88
Figure 4.4. Lateness Lower Bound Evaluation.................................................................... 93
Figure 4.5. Branch-and-Bound Algorithm........................................................................... 94
Figure 4.6. Scheduling Example 1 ...................................................................................... 95
Figure 4.7. Scheduling Example 2 ...................................................................................... 96
Figure 4.8. An uni-processor example from [119] .............................................................. 97
Figure 5.1. Partitioning process (highlighted)................................................................... 100
Figure 5.2. Pre-partitioning algorithm............................................................................... 102
Figure 5.3. Application of the function PrecedenceAdjustOrPartition()........................... 105
Figure 5.4. Application of the function ExclusionAdjustOrPartition()............................. 106
Figure 5.5. Feasible partitioning........................................................................................ 107
Figure 5.6. System specification........................................................................................ 113
Figure 5.7. Adjusted Specification .................................................................................... 114
Figure 5.8. Schedule after pre-partitioning........................................................................ 114
Figure 5.9. Final scheduling results................................................................................... 115
Figure 6.1. Pump Controller’s initial net specification ..................................................... 119
Figure 6.2. Pump Controller at the scheduling level ......................................................... 121
Figure 6.3. Pump Controller’s partial scheduling results .................................................. 122
Figure 6.4. Motor Control Net........................................................................................... 124
Figure 6.5. Speed Control Subnet...................................................................................... 124
Figure 6.6. Torque Control Subnet.................................................................................... 125
Figure 6.7. Integrator Subnet............................................................................................. 125
Figure 6.8. Motor flat net .................................................................................................. 125
Figure 6.9. Speed Control specification for operation-level scheduling ........................... 127
Figure 6.10. Schedule of Case 1........................................................................................ 128
Figure 6.11. Schedule of Case 2........................................................................................ 128
Figure 6.12. York1 and York2 Specification Net.............................................................. 129
Figure A.1. A simple Cab net............................................................................................ 145
Figure A.2. Simulation Recording Tool ............................................................................ 147
Figure B.1. Store equivalents when used for input or output............................................ 149
Figure B.2. Store and periodic transitions ......................................................................... 149
 S.V. Cavalcante
___________________________________________

Figure B.3. Mutual exclusion, input and output places......................................................150

Figure B.4. Subnet equivalent............................................................................................150
S.V. Cavalcante 
___________________________________________

,IST OF 4ABLES

Table 2.1. Summary of co-design approaches..................................................................... 41

Table 4.1. Relations inconsistencies.................................................................................... 82
Table 5.1. Possible Solutions ............................................................................................ 113
Table 5.2. Tasks initial timing information ....................................................................... 113
Table 5.3. Release times and deadlines after adjustments................................................. 114
Table 5.4. Pre-partitioning................................................................................................. 114
Table 5.5. System partitioning........................................................................................... 114
Table 6.1. Pump Controller’s periodic tasks ..................................................................... 118
Table 6.2. Pump Controller’s timing specification ........................................................... 119
Table 6.3. Pump Controller’s refined timing specification ............................................... 121
Table 6.4. Motor timing specifications.............................................................................. 123
Table 6.5. York1 Timing and Architectural Specification ................................................ 130
Table 6.6. York2 Timing and Architectural Specification ................................................ 132
 S.V. Cavalcante
___________________________________________

!CKNOWLEDGEMENTS

This work was made possible by the funding of CAPES - Brazilian Research
Agency - under the project number 2779/92-8.

Many thanks to my wife for her support, love, care, understanding, and
encouragement during our life together and specially throughout the development of this
dissertation.

I am deeply indebted to my parents not only for their continual understanding and
encouragement but also for the material support which provided me with conditions to
reach this point in my carrier.

Thanks to my supervisor, Prof. David J. Kinniment, for his help and encouragement
throughout the development of the project.

Thanks to all staff from the Department of Electrical and Electronic Engineering of
the University of Newcastle upon Tyne for their help. In particular, many thanks to Dr.
Gordon Russell for his invaluable guidance and friendship.

Thanks to Prof. Mauro Pezzé from the Politecnico de Milano, Italy, for providing
the Cabernet environment and making its source code available.

My gratitude to Rogério de Lemos, Avelino Zorzo, and Marinho Barcellos for the
discussions about the methodology. Thanks to Shirley Craig, the best librarian I have ever
met, for the care and interest in forwarding all new information related to my topic which
reached her hands.

Thanks to the many friends I made here, specially those from the Luso-Brazilian-
Society, for great moments and the relaxation necessary to cope with the stress.
S.V. Cavalcante 
___________________________________________

! 0ATRICIA

AOS MEUS PAIS

A *ºLIA
 S.V. Cavalcante
___________________________________________
 

)NTRODUCTION

The high complexity found in current digital systems requires new tools and methodologies
for design. By working at higher abstraction levels the designer can be kept from design
details which can be handled by automated tools in CAD environments. The automation of
low level tasks also helps to produce correct designs, which further reduces the overall
design time and cost. Market competition produces a strong request for productivity. The
damage in profitability due to a six month delay in a product release can be worse than a 50
per cent cost overrun during the design cycle [103]. At the same time, market pressures
make it necessary to produce more adaptable and changeable hardware devices (hardware
to software migration) and more performance efficient software systems (software to
hardware migration).

In order to handle this complexity and productivity need, an approach called

HARDWARE SOFTWARE CO DESIGN has become a hot research topic since the beginning of the
decade. This approach is aimed to the co-development of the hardware and software parts
of digital systems, promoting a better integration between those parts, and reducing cost
and time-to-market by using defined methodologies and CAD tools.

Although co-design is not new, its development has been made possible by the
availability of techniques, such as hardware high-level synthesis, which puts hardware
 S.V. Cavalcante
Chapter 1: Introduction
___________________________________________

development at an abstraction level nearer to that found in software development [117].

Furthermore, the advent of application-specific integrated circuits (ASICs) and field
programmable gate arrays (FPGAs) has helped to change the boundary between software
and hardware. This boundary has become fuzzier and techniques once used for software
development have started to be used for hardware as well.

 %MBEDDED 3YSTEMS AND #O $ESIGN

Co-design is being used in several applications, from the design of general-purpose

processors and compilers to embedded digital systems. In the particular case of embedded
systems, the design starts with a high-level functional description where implementation
details are not taken into account. As the design proceeds, the system is split into hardware
and software partitions. The choice on the best partitioning depends on characteristics
required to be present at the final system implementation, such as area, speed, and
upgradability requirements. Analysis techniques are used to estimate values for the design
features, validate refinements, profiling of systems, etc. Due to the large number of
different solutions that may be produced, the co-design process needs to allow for constant
interaction with the user in order to guide the solution space exploration.

There has been an enormous increase in the number of systems which use dedicated
processors. Examples of such systems are camcorders, microwave ovens, mobile phones,
fax machines, printers, cash machines, and industrial control systems. It is a rapidly
expanding market, as shown in Figure 1.1. Co-design is likely to play a major role in the
development of such devices [35]. However, there are still many problems of interest to be
tackled.

Most specification methods used in co-design start with an initial language which is
translated to an internal representation. This method makes it difficult for the designer to
follow the design process. A useful characteristic would be the use of a single
representation from the high-level specification through to hardware synthesis and software
compilation.
S.V. Cavalcante 
Chapter 1: Introduction
___________________________________________

53 BILLIONS
 4OTAL 'ROWTH INC $30S



 5P TO  BIT




 5P TO  BIT

 5P TO  BIT


           

&IGURE  7ORLD WIDE REVENUES FOR MICRO CONTROLLERS AND $30 SALES ;=

Architectures comprising multiple software processors are not common in co-

design. Figure 1.2 shows a basic co-design architecture which is used by several authors
(e.g. in [8, 52]). The use of several processors particularly benefits rapid prototyping by
allowing the system to be emulated using minimal specially built hardware.

Micro-Processor ASIC 1

Memory ASIC 2

&IGURE  "ASIC CO DESIGN ARCHITECTURE

The general approach used in this area includes the exploration of hardware-
software characteristics such as area, speed, memory limitations, power consumption,
maintainability, upgradability, testability, reliability, etc. However, most of the systems
developed so far do not consider critical real-time issues explicitly, or when they do so
there are many restrictions such as not allowing more then a task to operate at the same
 S.V. Cavalcante
Chapter 1: Introduction
___________________________________________

time on the architecture. This is done to overcome the difficulty of guaranteeing time
properties in multi-processor architectures. However, in this approach the only advantage
in implemented tasks in hardware is the execution speed-up of each task but no advantage
in parallelism exploitation exists.

When it comes to time critical systems there must be analysis methods to guarantee
that the requirements are met. Furthermore, any automatic partitioning algorithm targeted
to such systems needs to take time issues into consideration in order to make decisions
which would increase the probability of finding feasible architectures.

 /BJECTIVES OF 4HIS $ISSERTATION

Based on the above discussion, the target systems to be dealt with in this dissertation are
embedded real-time applications. As such, the primary objectives are:

• To provide more flexibility in the basic architecture by allowing several different

software processors to operate concurrently. This would permit the use of the best
type of processor to each application, e.g. DSPs, micro-controllers, etc.

• To tackle the problem of dealing with real-time constraints in co-design, while

permitting parallelism among partitions and processors.

• The use of a single, simple, neutral specification language. This language should
follow the trend of using graphical design methods. At the same time it needs to
permit real-time requirement specifications. The neutrality mentioned before refers
to the ability of modelling hardware and software tasks without imposing any bias.
It needs to allow for refinements to be done from the initial abstraction level down
to the generation of models for hardware synthesis and software compilation.

 0ROPOSED -ETHOD

In order to achieve the objectives mentioned, the following approach is used here:

• Use of a well-established graphical formalism as the basis of the specification

formalism. Specifically, Petri nets [93] are being utilised here due to their
widespread use in several areas, from concurrent system analysis and specification
to hardware synthesis. Also, Petri nets have formal semantics which allows for the
development of formal analysis techniques and transformations. Nevertheless,
S.V. Cavalcante 
Chapter 1: Introduction
___________________________________________

extensions to the formalism were necessary in order to provide the facilities

required for the co-design approach used here.

• Use of a task scheduler in order to verify time properties. A new algorithm was
developed in order to allow for the pre-runtime scheduling of sets of tasks
distributed over a multi-processor architecture. Tasks with release times, deadlines
and inter-task dependencies such as precedence, mutual exclusion, and pre-emption
relations are considered. The algorithm is also used to produce information for the
partitioning phase.

• A dual-phase automatic partitioning is being applied, where starting from an

unfeasible specification, tasks are moved to hardware in an attempt to produce a
feasible solution. The partitioning phases are:

1. Pre-Partitioning: This takes care of individual-task time constraints and

constraints generated by inter-task dependencies. These constraints can be
solved only by execution speed-up, i.e. by moving tasks to hardware
(movement of tasks among software processors are not performed by the
system).

2. System Partitioning: This is concerned with problems derived from excessive

software processor utilisation, i.e. contention for the use of a same resource by
several tasks. At this phase, the speed-up gain when moving a task to hardware
is interesting but not strictly required. The parallelism acquired when moving
tasks to other hardware processors is enough to solve real-time problems here.

 /RGANISATION OF THE $ISSERTATION

Chapter 2 provides an overview on the state-of-the-art in hardware-software co-design and

an introduction to issues of importance to the proper understanding of this dissertation,
such as Petri nets and real-time systems.

The general co-design methodology proposed here is shown in Chapter 3. In

particular, the specification formalism is presented together with the graphical CAD tool
which implements it. This tool is used for design specification and initial architecture
selection, which may present more than one software processor. Tasks may also be initially
allocated to any hardware device (e.g. ASICs) that the user specifies. New hardware
 S.V. Cavalcante
Chapter 1: Introduction
___________________________________________

devices are created during partitioning, if necessary, to guarantee the schedulability of the
system.

The methodology is also used to guide the refinements necessary to produce an

output suitable to be used by the scheduling and partitioning algorithms. This guidance is
performed through consistency checks performed by the CAD tool which compares the
design with the rules imposed for the generation of the output model.

The scheduling algorithm is presented in Chapter 4. It is able to find a solution,

whenever one exists, for the scheduling of a set of processes with deadlines, release times,
precedence, exclusion relations, and which allows process pre-emption, in a heterogeneous
multi-processing architecture. It is based on a branch-and-bound technique developed by
Xu and Parnas [119].

Chapter 5 presents the partitioning algorithm developed to tackle real-time

constraints. Two definitions are key to the proper understanding of the partitioning
approach proposed:

1. A process implementation is considered feasible if, in the absence of resource

constraints, its related time constraints are met. This is dealt with during pre-
partitioning.

2. A whole system is considered feasible if all its processes are feasible and there
exists an allocation and scheduling of those processes such that the time
constraints are met. System feasibility is considered during system partitioning.

Some examples of the use of the methodology are presented in Chapter 6. A

mixture of academic and real-life designs are employed to enhance specific characteristics
of the co-design approach developed in this dissertation.

Finally, general conclusions and plans for future work are presented in Chapter 7.