Soto Maria Rossi Andr? Laurent Johann Sevaux Marc - Memory allocation problems in embedded systems: optimization methods

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 Ltd
27-37 St Georges Road
London SW19 4EU
UK
www.iste.co.uk

John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com

ISTE Ltd 2013

The rights of Mara 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.

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 designers 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 systems 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.

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.

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: