Memory Allocation Problems in Embedded Systems E-Book

Maria Soto

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 193

Veröffentlichungsjahr: 2013

Beschreibung

Embedded systems are everywhere in contemporary life and are supposed to make our lives more comfortable. In industry, embedded systems are used to manage and control complex systems (e.g. nuclear power plants, telecommunications and flight control) and they are also taking an important place in our daily activities (e.g. smartphones, security alarms and traffic lights). In the design of embedded systems, memory allocation and data assignment are among the main challenges that electronic designers have to face. In fact, they impact heavily on the main cost metrics (power consumption, performance and area) in electronic devices. Thus designers of embedded systems have to pay careful attention in order to minimize memory requirements, thus improving memory throughput and limiting the power consumption by the system's memory. Electronic designers attempt to minimize memory requirements with the aim of lowering the overall system costs. A state of the art of optimization techniques for memory management and data assignment is presented in this book.

Leseprobe

Table of Contents

Introduction

Chapter 1 Context

1.1. Embedded systems

1.2. Memory management for decreasing power consumption, performance and area in embedded systems

1.3. State of the art in optimization techniques for memory management and data assignment

1.4. Operations research and electronics

Chapter 2 Unconstrained Memory Allocation Problem

2.1. Introduction

2.2. An ILP formulation for the unconstrained memory allocation problem

2.3. Memory allocation and the chromatic number

2.4. An illustrative example

2.5. Three new upper bounds on the chromatic number

2.6. Theoretical quality assessment of three upper bounds

2.7. Computational assessment of three upper bounds

2.8. Conclusion

Chapter 3 Memory Allocation Problem With Constraint on the Number of Memory Banks

3.1. Introduction

3.2. An ILP formulation for the memory allocation problem with constraint on the number of memory banks

3.3. An illustrative example

3.4. Proposed metaheuristics

3.5. Computational results and discussion

3.6. Conclusion

Chapter 4 General Memory Allocation Problem

4.1. Introduction

4.2. ILP formulation for the general memory allocation problem

4.3. An illustrative example

4.4. Proposed metaheuristics

4.5. Computational results and discussion

4.6. Statistical analysis

4.7. Conclusion

Chapter 5 Dynamic Memory Allocation Problem

5.1. Introduction

5.2. ILP formulation for dynamic memory allocation problem

5.3. An illustrative example

5.4. Iterative metaheuristic approaches

5.5. Computational results and discussion

5.6. Statistical analysis

5.7. Conclusion

Chapter 6 MemExplorer: Cases Studies

6.1. The design flow

6.2. Example of MemExplorer utilization

Chapter 7 General Conclusions and Future Work

7.1. Summary of the memory allocation problem versions

7.2. Intensification and diversification

7.3. Conclusions

7.4. Future works

Bibliography

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKwww.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.wiley.com

© ISTE Ltd 2013

The rights of María Soto, André Rossi, Marc Sevaux and Johann Laurent to be identified as the author of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2012951962

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-428-6

Introduction

This book addresses four memory allocation problems. The following sections present the motivations, the main contributions and the outline of this book.

Motivations

Embedded systems are ever present in contemporary society and they are supposed to make our lives more comfortable. In industry, embedded systems are used to manage and control complex systems (e.g. nuclear power plants, telecommunication, and flight control; they are also playing an important role in our daily activities (e.g. smartphones, security alarms and traffic lights).

The significant development in embedded systems is mainly due to advances in nano technology. These continuous advances have made possible the design of miniaturized electronic chips, leading to drastically extend the features supported by embedded systems. Smartphones that can surf the Web and process HD images are a typical example. In addition to market pressure, this context has favored the development of computer-aided design (CAD) software, which brings a greater change to the designer’s line of work. While technology offers more and more opportunities, the design of embedded systems becomes more and more complex. Indeed, the design of an integrated circuit, whose size is calculated in billions of transistors, thousands of memories, etc., requires the use of competitive computer tools. These tools have to solve optimization problems to ensure a low cost in terms of area and time, and they must meet some standards in electronics.

Currently, in the electronics industry, the problems are often addressed using either ad hoc methods based on the designer expertise or general methods (typically genetic algorithms). But both methods do not work well in solving large-scale industrial problems.

On the other hand, computer-aided design software such as Gaut [GAU 93, COU 06] has been developed to generate the architecture of a chip (circuit) from its specifications. While the design process is significantly faster with these types of software, the generated layouts are considered to be poor on power consumption and surface compared to man-made expertly-designed circuits. This is a major drawback as embedded products have to feature low-power consumption.

In the design of embedded systems, memory allocation and data assignment are among the main challenges that electronic designers have to face. Indeed, they deeply impact on the main cost metrics (power consumption, performance and area) in electronic devices [WUY 96]. Thus, designers of embedded system have to carefully pay attention to minimize memory requirements, improving memory throughput and limiting the power consumption by the system’s memory. Electronic designers attempt to minimize memory requirements with the aim of lowering the overall system costs.

Moreover, the need for optimization of the allocation of data structures is expected to become even more stringent in the future, as embedded systems will run heavy computations. As an example, some cell phones already support multi-threading operating systems.

For these reasons, we are interested in the allocation of data structures into memory banks. This problem is rather difficult to handle and is often left to the compiler with which automatic rules are applied. Nevertheless, an optimal allocation of data to memory banks may lead to greater savings in terms of running time and energy consumption.

As has often been observed in microelectronics, this complex problem is poorly modeled or not modeled at all. The proposed solutions are based on a lower modeling level that often only considers one objective at a time. Also, the optimization of methods is little (or not) quantified, only the running time is available and assessed. Thus, the models and data are not analyzed much.

In this book, we model this problem and propose optimization methods from operations research for addressing it.

Contribution

In memory management and data assignment, there is an abundant literature on the techniques for optimizing source code and for designing a good architecture for an application. However, not much work looks at finding a good allocation of data structure to memory banks. Hence, the first contribution of this book is the introduction of four versions of memory allocation problems, which are either related to designing the memory architecture or focused on the data structure assignment.

The second important contribution of this book is the introduction of three new upper bounds on the chromatic number without making any assumption on the graph structure. These uppers bounds are used to address our first memory allocation problem.

The third contribution is the design of exact mathematical models and metaheuristic approaches to address these versions of the memory allocation problem. Additionally, the proposed metaheuristics are compared with exact methods on a large set of instances.

Finally, in order to achieve this work, we have undertaken some challenges between operations research and electronics. Thus, this book aims at contributing to reducing the gap between these two fields and these two communities.

Outline

The problems addressed in this book are presented by increasing complexity, with the aim of smoothly introducing the reader to these problems; each version of the memory allocation problem is separately developed in different chapters. This book is organized as follows:

– Chapter 1 describes the general context in which this work has been conducted. We highlight the strong dependence of contemporary society on embedded systems. A state of the art of optimization techniques for memory management and data assignment is presented. We discuss the benefits of using operations research for electronic design.

– Chapter 2 presents the first version of the memory allocation problem. The work presented in this chapter has been presented in detail [SOT 09], and was published in the journal Discrete Applied Mathematics.

– Chapter 3 deals with the second version of the memory allocation problem. This is the allocation of data structures into memory banks while making minimum hypotheses on the targeted chip. The main characteristic in the memory architecture is that the number of memory banks is fixed. The work around this problem has been published as a long article in Roadef 2010 [SOT 10].

– Chapter 4 addresses the general memory allocation problem. This problem is more realistic than the previous problem; in addition to memory banks, an external memory is considered in the target architecture. Moreover, more constraints on memory banks and data structures are considered. The work about the general memory allocation problem has been published in the Journal of Heuristics [SOT 11a].

– Chapter 5 deals with the last version of the memory allocation problem. This problem is concerned with dynamic memory allocation; it has a special emphasis on time performance. A memory allocation must consider the requirement and constraints at each time interval, that is it can be adjusted to the application needs at each time interval. This problem has been presented at EVOCOP 2011 [SOT 11c].

– Chapter 6 presents a general conclusion to this work; it discusses results and provides ideas for future work.

– Chapter 7 discusses the implementation of this work in a software called Softexplorer. It is available free at http://www.softexplorer.fr/.

Chapter 1

Context

This chapter describes the general context in which this work has been conducted, how our work takes its roots and how this research can be placed in the field of electronic design.

In section 1.1 of this chapter, we highlight the importance nowadays of embedded systems. Section 1.2 stresses the relationship between memory management and three relevant cost metrics (such as power consumption, area and performance) in embedded systems. This explains the considerable amount of research carried out in the field of memory management. Then, the following section presents a brief survey of the state of the art in optimization techniques for memory management, and, at the same time, positions our work with respect to the aforementioned techniques. Finally, operations research for electronic design is taken into consideration for examining the mutual benefits of both disciplines and the main challenges exploiting operations research methods to electronic problems.