Memory Allocation Problems in Embedded Systems- Optimization Methods (ISTE).pdf

MemoryAllocationProblemsinEmbeddedSystems

MemoryAllocationProblems

EmbeddedSystems

OptimizationMethods

MaríaSoto

AndréRossi

MarcSevaux

JohannLaurent

SeriesEditor

NarendraJussien

Firstpublished2013inGreatBritainandtheUnitedStatesbyISTELtdandJohnWiley&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 formor 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

undermentionedaddress:

ISTELtd

JohnWiley&Sons,Inc.

27-37StGeorge’sRoad

111RiverStreet

LondonSW194EU

Hoboken,NJ07030

USA

www.iste.co.uk

www.wiley.com

©ISTELtd2013

The rights of María Soto, André Rossi, Marc Sevaux and Johann Laurent to be identified as the author of

thisworkhavebeenassertedbytheminaccordancewiththeCopyright,DesignsandPatentsAct1988.

LibraryofCongressControlNumber: 2012951962

BritishLibraryCataloguing-in-PublicationData

ACIPrecordforthisbookisavailablefromtheBritishLibrary

ISBN:978-1-84821-428-6

PrintedandboundinGreatBritainbyCPIGroup(UK)Ltd.,Croydon,SurreyCR04YY

TableofContents

Introduction .......................... ix

Chapter 1. Context ...................... 1

1.1. Embeddedsystems .................. 2

1.1.1. Maincomponentsofembeddedsystems .. 3

1.2. Memorymanagementfordecreasingpower

consumption,performanceandareain

embeddedsystems .................. 4

1.3. Stateoftheartinoptimizationtechniquesfor

memorymanagementanddataassignment .. 8

1.3.1. Softwareoptimization ............. 9

1.3.2. Hardwareoptimization ............ 11

1.3.3. Databinding ................... 16

1.3.3.1. Memorypartitioningproblemforlow

energy ..................... 17

1.3.3.2. Constraintsonmemorybankcapacities

andnumberofaccessestovariables .. 18

1.3.3.3. Usingexternalmemory .......... 19

1.4. Operationsresearchandelectronics ....... 21

1.4.1. Mainchallengesinapplyingoperations

researchtoelectronics ............. 23

vi MemoryAllocationProblemsinEmbeddedSystems

Chapter 2. Unconstrained Memory Allocation

Problem ............................. 27

2.1. Introduction ...................... 28

2.2. AnILPformulationfortheunconstrained

memoryallocationproblem ............. 31

2.3. Memoryallocationandthechromaticnumber . 32

2.3.1. Boundsonthechromaticnumber ...... 33

2.4. Anillustrativeexample ............... 35

2.5. Threenewupperboundsonthechromatic

number ......................... 38

2.6. Theoreticalassessmentofthree

upperbounds ..................... 45

2.7. Computationalassessmentofthree

upperbounds ..................... 49

2.8. Conclusion ....................... 53

Chapter 3. Memory Allocation Problem With

Constraint on the Number of Memory Banks ... 57

3.1. Introduction ...................... 58

3.2. AnILPformulationforthememoryallocation

problemwithconstraintonthenumberof

memorybanks ..................... 61

3.3. Anillustrativeexample ............... 64

3.4. Proposedmetaheuristics .............. 65

3.4.1. Atabusearchprocedure ............ 66

3.4.2. Amemeticalgorithm .............. 69

3.5. Computationalresultsanddiscussion ...... 71

3.5.1. Instances ..................... 72

3.5.2. Implementation ................. 72

3.5.3. Results ...................... 73

3.5.4. Discussion .................... 75

3.6. Conclusion ....................... 75

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: