RealTime Embedded Systems

实时嵌入式系统电子书。学习嵌入式系统的重要教材。This page intentionally left blankReal-TimeEmbedded systemsOptimization, Synthesis, and NetworkingMeikang QiuayinCRCCRC Pressaylor Francis GroupBoca Raton London New YorkCRC Press is an imprint of theTaylor Francis Group an informa businessA ChaPMan HALL booKCRC PressTaylor Francis group6000 Broken Sound Parkway NW, Suite 300Boca raton FL 33487-2742o 2011 by Taylor Francis Group, LLCCRC Press is an imprint of Taylor Francis Group, an Informa businessNo claim to original U.S. Government worksInternational Standard Book Number-13: 978-1-4398-1765-0(eBook-PDF)This book contains information obtained from authentic and highly regarded sources. Reasonableefforts have been made to publish reliable data and information, but the author and publishassume responsibility for the validity of all materials or the consequences of their use. The authors andpublishers have attempted to trace the copyright holders of all material reproduced in this publicationand apologize to copyright holders if permission to publish in this form has not been obtained. If anycopyright material has not been acknowledged please write and let us know so we may rectify in anyfuture reprint.Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproducedtransmitted, or utilized in any form by any electronic, mechanical, or other means, now known orhereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishersFor permission to photocopy or use material electronically from this work, pleccesswww.coprightcom(http://www.copyright.com/)orcontacttheCopyrightClearanceCenter,Inc.(ccc),222Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a phetocopy license by the CCC, a separate system of payment has been arrangedTrademark Notice: Product or corporate names may be trademarks or registered trademarks, and areused only for identification and explanation without intent to infringeVisit the taylor francis Web site athttp://www.taylorandfrancis.comand the crc Press Web site athttp://www.crcpress.comContentsPrefaceAcknowledgmentsAuthors1 Introduction to Real-Time Embedded Systems1.1 Embedded Systems Overview1.1.1 Processor Tcchnology1.1.2 Design Technology1.1.3 MemoTechnolog1.1.4 Design Challenge-Optimizing Design Metrics11234561.2 Fixed Time Model of lleterogeneous Embedded Systems1.3 Probabilistic Time Model of Heterogeneous Embedded Systems 91.3.1 Background and Example1.3.1.1 System Model121.3.1.2 Example121.3.2 The Algorithms for the hap problem141.3.2.1 Definitions and lemma141.3.2.2 A Ileuristic Algorithm for Dag171.3.2.3 An Optimal Algorithm for DAg181.3.3 Experiment201.4 Conclusion1.5 Glossary232 Optimization for Real-Time Embedded Systems252.1 Introduction2.2 Related Work262.2. 1 Heterogeneous Embedded Systems262.2.2 Time and Power Optimization282.3 Graph Models and Timing Optimization2.3.1 Basic Graph models and techniques302.3.2 Timing optimization2.3.3 Timc and Powcr Optimizations352.3.3. 1 Loop Scheduling and Parallel Computing.. 352.3.3.2 Motiva.tiona l Examples38ontents2.4 Collus2.5 Glossary423 Multicore Embedded Systems Design433.1 Introduction3. 2 Basic Ce463.2.1 The Architecture model463.2.2 The Memory Modcl483.2.3 MDFG and Rotation Scheduling3.2.4 Partitighe iteration si513.2.4.1 Partition S523.2.4. 2 The Memory Size3. 2.5.1 Type Assignment for Memory Only3.2.5 Type Assignment533.2.5.2 Type Assignment for Core and MemoryTogether3.3 The Algorithms3.3.1 The LSM Algorithn563.3.2 The Type_Assign Algorithm583.3.2.1 Definitions and Lemma of Type- assign3.3.2.2 The Type_Assign Algorithm603.3.2.3 The Minimum Resource Scheduling andConfiguratiOn603.4 Experim633.5 Conclusion663.6 Glossary4 Resource Allocation with Inaccurate information674.1 Introduction674.2RWork684.3 Model and definitie4.3.1 Stochastic Model4.3.2 Measurement Parameters714.4 Algorith724.4.1 Overview724.4.2MCT724.4.3 Min-mi724. 4. 4 Max-Min734.5 Simulation744.5.1 Simulation Setup744.5.2 Simulation Results754.5.2.1C0mthe Impacts on robWhModifying different Parameters754.5.2.2 Compare the Performance of DifferentHeuristics76ContentsV114.6 Couclusion795 Heterogeneous Parallel Computing815.1 Introduction815.2.1 Fixed Hardware Platform Model of Heterogeneous. 855.2 Motivational exampleEmbedded Systcms5. 2. 2 Configurable Hardware Platform, Fixed/ Non-FixedExecution time model865.3 System Model885.4 The Algorithm to Optimize Heterogeneous Embedded Systems 915.4.1 Definitions and lemma915.4.2 The OESCP Algorithm45.4.3 Complexity of Algorithm OESCP945.5 Experiments955.6 Conclusion5.7 Glose6 Scheduling for Phase Change Memory with Scratch PadMemory996.1 Introduction996.2 Modcls and Basic Concepts1026.2.1 Architecture Model106.2.2 DFG Model1036.2.3 Retiming and Rotation Scheduling1056.3 Problem Statement1066. 4 Algorithms6.4.1 High Access Frequency First(HAFF) Variable Partition 1086.4.2 Global View Prediction(GVP) Variable Partition1106.4.3 Loop Pipeline scheduling1166.5 Experiments1196.6 Conclusion1226.7Gl1237 Task Scheduling in Multiprocessor to Reduce PeakTemperature1257.1 Introduction1257.2 Related Work1267.3 Model and Background1277.3.1Th1277. 3. 2 The 3D CMP and the Core Stack7.3.3 Application Model1307. 4 Motivational e1317.4.1 An Example of Task Scheduling in CMP131ontents7.4.2 List Scheduling Solution1324.3 Improved Solution1327.5 Thermal-Aware Task Scheduling Algorithm1357.5.1 The TARs Algorithm1357.5.2 The Ptmm algorithm1367.5.3 The MPTSS Algorithm1367.5.4 The RS al1377.6 Experimental Results1387.6.1Eyxperiment Setup1397. 7 Conclusion1417.8Gl1418 Networked Sensing and Monitoring Systems1438.1 Introduction1438.2 Models1458.2. 1 Heterogeneous FU Schedule ProbleIn1458.2.2 The virtuaI Sensor network modell468.3 The Algorithms1488.3.1.1 Sensor Scheduling with Bipartite Matching. 1488.3.1 Task-Sensor Scheduling8.3.1.2 Sensor Scheduling with Progressive Relaxation 1518.3.2 Adaptive Energy-Aware Online Algorithm1518.3.2.1 AOEs Algorithm1538.3.2.2 MAP-_CP Algorithm1538.3.2.3 MAP_Opt Algorithm1548.4 Experiments1568.5 Conclusion1588.6 Glossary1589 Battery-A ware Scheduling for Wireless Sensor Network 1599. 1 Introduction1599.2 Related work1609.3 Background and Model1619.3. 1 Application Model1619.3.2 Network model1619.3.3 Battery Behavior and Energy Constraint1639.4 Two-Phase List-Scheduling Algorithms1659.4.1 Phase I: DaG List Scheduling1669.4.2 Phase ll: Constraint-Aware Reassigning1669.5 Experimental results1699.5. 1 Experiment Setup1699.5.2 Result9. 6 Conclusion1749.7 Glossary17410 Adaptive Resource Allocation in Cloud Systerms17510. 1 Introduction17510.2RWork17610.3 Model and background17710.3.1 Cloud System17710.3.2 Resource allocation model17810.3.3 Job model17810.4 Resource AllocatiOn and Task Scheduling AlgorithIll17910.4.1 Static Resource allocation17910.4.1.1 Cloud List Scheduling(ClS18010.4. 1.2 Cloud Min-Min Scheduling(CMMS18010.4.1.3 Local resource allocation18110.4.2 Online Adaptive Scheduling10.5 Experimental Results18310.5.1 Experiment Setup18310.5.2 Result18410.6 Conclusion18610.7 Glossary186Bibliography187