Modeling, Verification and Exploration of Task-Level Concurrency in Real-Time Embedded Systems / Edition 1

by Filip Thoen, Francky Catthoor

Overview

system is a complex object containing a significant percentage of elec­ A tronics that interacts with the Real World (physical environments, humans, etc. ) through sensing and actuating devices. A system is heterogeneous, i. e. , is characterized by the co-existence of a large number of components of disparate type and function (for example, programmable components such as micro­ processors and Digital Signal Processors (DSPs), analog components such as AID and D/A converters, sensors, transmitters and receivers). Any approach to system design today must include software concerns to be viable. In fact, it is now common knowledge that more than 70% of the development cost for complex systems such as automotive electronics and communication systems are due to software development. In addition, this percentage is increasing constantly. It has been my take for years that the so-called hardware-software co-design problem is formulated at a too low level to yield significant results in shorten­ ing design time to the point needed for next generation electronic devices and systems. The level of abstraction has to be raised to the Architecture-Function co-design problem, where Function refers to the operations that the system is supposed to carry out and Architecture is the set of supporting components for that functionality. The supporting components as we said above are heteroge­ neous and contain almost always programmable components.

Product Details

ISBN-13:	9780792377375
Publisher:	Springer US
Publication date:	11/30/1999
Edition description:	2000
Pages:	438
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Read an Excerpt

Chapter 1: Introduction

"By the year 2005, a designer will have to achieve a design productivity of one 16-bit processor per day if he wishes to satisfy market demand . . . "

- [anonymous]

The combination of VLSI process technology and Real-time Signal Processing (RSP) has brought a breakthrough in information technology (IT). The merging of computers, consumer and communication disciplines gives rise to very fast growing markets for personal communication, multi-media and broadband networks. Rapid evolution in sub-micron process technology allows ever more complex systems to be integrated on one single chip. Technology advances are however not followed by an increase in design productivity, causing technology to leapfrog the design of integrated circuits (ICs) and consumer markets. A consistent design technology that can cope with such complexity and with the ever shortening time-to-market requirements is of crucial importance [Tuck 97]. This design technology should support the realization of such digital VLSI systems for real-time information processing. It must encompass the methodology for designing such systems as well as the computer-aided design (CAD) tools and hardware/software libraries. Additionally, high-level behavioral models capturing the system behavior in an abstract and un-biased way are required allowing design space exploration and optimization. The real-time aspect of these RSP algorithms and of their implementation has not been given sufficient consideration.

Today, a new architectural design paradigm of including one or more programmable components, either general purpose or DSP processors, cores or ASIPs (application-specific instruction-set processor) as a component on these `systems-on-a-chip' is emerging. By this evolution, embedded processors become ubiquitous and a new role for embedded software in contemporary and future ASIC (application specific IC) systems is reserved.

In this book, a new automatable approach to the synthesis of real-time embedded systems is presented, with emphasis on performance and timing aspects (concurrency management and meeting of the timing constraints or `timeliness') while minimizing cost overhead. The main emphasis is on the task-level abstraction. We will motivate that at this abstraction level the distinction between `hardware synthesis' and `processor mapping/software synthesis' is practically gone and all steps in the design trajectory can then be shared for both target processor platforms (`hardware' and `software'). That enables a much more global design space exploration than in the traditional way. One of the major consequences is that the system cost can be significantly reduced and tighter timing/performance constraints can be met. In addition, the automation support can be mostly unified, which heavily reduces the man-power investment required in research, development and tool maintenance at this stage. In a more restricted context, some material in this book will however also use examples where the entire system is realized in `software'. In that case, we will mainly focus on `task-level software synthesis'.

In the first section of this introductory chapter, application trends, implementation architectures and the role of embedded software in embedded system design will be discussed. In the second section, the targeted application domain will be identified (Section 2.1), and the characteristics of real-time embedded systems will be explored (Section 2.2). Design problems and issues of embedded systems will be discussed in Section 2.3. A unified view on the global system design methodology problem, seen from a meta-level, will be briefly reviewed in Section 3. Next, in Section 4, the required CAD support to design these systems, and more specifically to synthesize real-time embedded systems at the task-level is identified. At that stage also the context of an encompassing unified meta-flow design trajectory will be described. Embedded software is used as a main illustration. The major issues lacking in current approaches will be briefly indicated as well, but the detailed discussion is postponed to Chapter 2. Finally, Section 5 will summarize the contributions of this book and present the outline to the remainder of the book.

1. Systems-On-A-Chip

Embedded Systems. Electronic systems, which use a computer to perform a specific function, but are neither used nor perceived as a computer, are generically known as embedded systems (ES). Typically, an ES performs a single function or is used to control a larger heterogeneous system [Hsieh 95]. Today, they are increasingly found in applications and services like automotive control, personal telecommunication and multi-media systems, consumer electronics, terminals for wireless communication (i.e. termination for cellular, WLAN or mobile satellite access, QAM based terminals), setupboxes for fixed network access (X-DSL twisted pair, CATV or LAN access) and video and image processing applications (MPEG-1/2/4, teleconferencing or HDTV)[Chiodo 95a][ETSI 94][Himbeeck 94].

Most of these applications are compact and portable devices, putting stringent constraints on the degree of integration (i.e. chip area) and on their power consumption. Secondly, these systems are extremely heterogeneous in nature and combine high performance data processing (e.g. data processing on transmission data input) as well as slow rate control processing (e.g. system control functions), synchronous as well as asynchronous parts, analog versus digital, . . . An example is given in Figure 1.1, depicting a mobile terminal for satellite voice and data communication [Himbeeck 94]. Thirdly, time-to-market has become a critical factor in the design phase. With a world-wide competition, typical product life cycle have gone down to 9 months in consumer electronics and only 18 months in telecommunication applications [Paulin 96], becoming equal or shorter than the product design time. Companies are faced with shrinking windows of opportunity, a late market introduction to the market eats a lot of the product's revenue. Together, they shorten the available design cycle dramatically. Fourthly, these systems are subjected to stringent real-time constraints, complicating their implementation considerable. The distinctive characteristic of these systems is the coexistence of two different types of functionalities, namely real-time signal processing and control functions, which require different timing constraint support. Specifically, signal processing functions operate on sampled data streams, and are subject to the real-time constraint derived from the required sample frequency or throughput. Control procedures vary in nature from having to be executed as soon as possible (like e.g. a man-machine interface), but an eventual execution delay does not usually compromise the integrity of the entire system (soft deadline), to having very stringent constraints, like e.g. a critical feedback control loop (hard deadline).

Heterogeneous architecture. Rapid advances in sub-micron process technology - more than 200 million transistors will be available by the year 2005 - allow to integrate complete systems on a single chip (`systems-on-a-chip') [Bursky 97]. Today it is has become more accepted to use (one or more) complete programmable components as macro-cells in the system's architecture, resulting in a heterogeneous architecture as depicted in Figure 1.2 [Bursky 94][Goossens 94][Goossens 96][Goossens 97][Paulin 96][Paulin 97]. Next to these programmable components, they contain specialized data paths (accelerators) and memory organizations (DRAM, SRAM, FIFOs, ... ), I/O peripherals, interface logic and more and more analog blocks as well. These programmable components run software components, being slow to medium speed algorithms, while time-critical parts are executed on dedicated hardware accelerators. The gray shading in Figure 1.2 corresponds to the functionality shading in Figure 1.1. However, a full-fledged general-purpose software component will probably perform too slowly and will even more likely be too costly and power-hungry for the medium to high-rate components (e.g. the audio layer in MPEG applications) due to its generalized computing structure. However, ASIPs may fill this niche [Sato 91][Goossens 95][Paulin 97]. This heterogeneous architecture recognizes the heterogeneous nature of embedded systems. As such, these systems have an architectural variability that far exceeds that of more predictable computer architectures and an equal or higher complexity. Consequently, they offer the potential of a much higher figure of merit in terms e.g. of the product of performance and (area/power) cost.

The advantages of including programmable components, typically in several styles, on chip are apparent.

• re-use: these components allow to employ the same block in different designs, resulting in an effective re-use of hardware, necessary because of the high cost of sub-micron processing, and a faster time-to-market, because of the higher design productivity.

• flexibility: is introduced in a dedicated ASIC solution, allowing to cope with design errors, last-minute changes (problematic with a 6 weeks processing turn-around for ASICs), incomplete specifications, product differentiation to satisfy the needs of different groups of consumers and easy evolution to next product generation.

• modular design style: however, compared with dedicated solutions, these architectures result in less efficient area and power implementations.

• system design complexity: this complexity is considerable reduced due to the presence of these large programmable building blocks. Furthermore, complex signal processing and/or micro-control is often better managed in software than in hardware. However, the first time design effort of the programmable component remains. Additionally, the design cost from a high-level specification to the low-level assembly level is a significant part of the total cost, as will be indicated below. Powerful and abstract tool support is needed as in the case of hardware design.

This evolution is supported by several vendors of fixed-point general-purpose DSP processors which announced the availability of their products in the form of such macro-cells (cores). This is the case e.g. for Texas Instruments (TMS320C25) and Motorola (M56000). Also, the semiconductor groups in telecommunication or consumer companies are designing fixed-point DSP cores, e.g. Philips (EPICS) [Beltman 95]. Finally, several new parameterizable DSP cores have been announced by "fab-less" companies, these are new players on the market, such as Zoran (Z385xx) [Bindra 95a], DSPGroup (Pine, Oak, Teak(lite) & Palm Core) [DSPGroup 97][DSPGroup 99], TCSI (LODE) [Bindra 95b], ARM (ARM7(TDMI), ARM9(TDMI), ARM10, StrongArm) [Ltd. 99] with fixed cores, and recently Arc Cores (ARC core) [Arc Cores 99] and Tensilica (Extensa) [Tensilica 98] with extensible and configurable cores...

Table of Contents

1. Introduction.- 1. Systems-on-a-chip.- 2. Heterogeneous real-time embedded systems.- 3. Unified meta design flow for multi-media and telecom applications.- 4. Design methodology & CAD design support.- 5. Overview of the book.- 2. Related Work and Contemporary Approaches.- 1. Manual approach.- 2. Real-time operating systems.- 3. Processor architecture integration.- 4. Task concurrency management.- 5. Motivation for a new approach.- 3. System Representation Model.- 1. Model requirements.- 2. Related Work — Models considering time.- 3. Basic Multi-Thread Graph model.- 4. MTG model extended with data communication.- 5. MTG model extended with timing.- 6. MTG model extended with hierarchy.- 7. Miscellaneous extensions.- 8. Advantages of the MTG model.- 9. Future extensions.- 10. Summary.- 4. Timing Analysis.- 1. Problem formulation.- 2. Related work — Timing verification.- 3. Related work — Timing analysis.- 4. Related work — Performance analysis.- 5. MTG classification.- 6. MTG separation analysis.- 7. MTG latency and response time analysis.- 8. MTG rate analysis.- 9. MTG boundedness analysis.- 10. Summary.- 5. System Synthesis Methodology.- 1. Methodology overview.- 2. MTG model extraction.- 3. Resource estimation.- 4. Task concurrency management — Thread frame clustering.- 5. Task concurrency management — Thread frame scheduling.- 6. Task concurrency management — Execution model selection.- 7. RTOS synthesis.- 8. Summary.- 6. Conclusions.- 1. Motivation.- 2. Contributions.- 3. Future work.- Appendices.- Definitions.- 1. Multi-sets.- 2. MTG definitions and properties.- 2.1 Definitions.- 2.2 Behavioral and structural properties.- 3. Algebras.- 3.1 Number algebras.- 4. Relations and partial orders.- 4.1 Binary relations.- 4.2 Partial orders.- 5. Automata.