Lecture Notes in Computer Science 3894 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Werner Grass Bernhard Sick Klaus Waldschmidt (Eds.) Architecture of Computing Systems – ARCS 2006 19th International Conference Frankfurt/Main, Germany, March 13-16, 2006 Proceedings 1 3 VolumeEditors WernerGrass BernhardSick UniversityofPassau Innstr.33,94032Passau,Germany E-mail:{grass,sick}@fmi.uni-passau.de KlausWaldschmidt UniversityofFrankfurt/Main Robert-Mayer-Str.11-15,60325Frankfurt,Germany E-mail:[email protected] LibraryofCongressControlNumber:2006921397 CRSubjectClassification(1998):C.2,C.5.3,D.4,D.2.11,H.3.5,H.4,H.5.2 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-32765-7SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-32765-3SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11682127 06/3142 543210 Preface Technologicalprogressis one of the driving forces behind the dramatic develop- mentofcomputersystemarchitecturesoverthepastthreedecades.Eventhough it is quite clear that this development cannot only be measured by the maxi- mum number of components on a chip, Moore’s Law may be and is often taken asasimple measureforthe non-brakedgrowthofcomputationalpoweroverthe years. The more components are realizable on a chip, the more innovative and unconventional ideas can be realized by system architects. As a result, research in computer system architectures is more exciting than ever before. Thisbookcoversthetrendsthatshapethefieldofcomputersystemarchitec- tures.Thefundamenataltrade-offinthedesignofcomputingsystemsisbetween flexibility,performance,powerconsumption,andchiparea.Thefullexploitation of future silicon capacity requires new architecture approaches and new design paradigmssuchas multiple computersona single chip,reconfigurableprocessor arrays, extensible processor architectures, and embedded memory technologies. For a successful use in practicalapplications,it is not enough to solvethe hard- wareproblemsbutalsotodevelopplatformsthatprovidesoftwareinfrastructure and support effective programming. A quantum jump in complexity is achieved by embedded computing systems with an unprecedented level of connectivity linking together a growing num- ber of physical devices through networks. Embedded systems will become more and more pervasive as the component technologies become smaller, faster, and cheaper.Their complexity arises not only fromthe largenumber ofcomponents but also from a lack of determinism and a continual evolution of these systems. The research effort needed to design systems so that they can be developed, deployed, maintained, configured, managed, and trusted will be a key issue for many years. Pervasive computing is therefore much more than an Internet ac- cess by mobile devices.The papers presentedin this book set outthe broadness of the research area established by pervasive computing approaches: input de- vicesforwearablesystems,mobilecollaborativeapplications,measurementdata acquisition, location awareness,QoS awareness,and context awareness. One possibility to cope with the growing complexity of computing systems is to make them organic or autonomous, that is, to make them self-learning, self-organizing,self-configuring,self-optimizing,self-healing,self-protecting,and proactive. Inthiscontext,completelynewproblemsarisethatshouldbeaddressedbyan interdisciplinary effort. Natural organic and self-organizing systems have been studied in other scientific discplines such as philosophy and biology, and their results should now be considered by architects of organic computing systems. Some of the key questions are: VI Preface 1. Doorganicsystemsfeaturepropertiesthatcannotbederivedfromtheprop- erties of its components? Is this emergent behavior desirable in any case or not? 2. Can we really expect to completely control systems with an emergent be- havior? 3. Whichmathematicalformalismscanhelpinconstructingandanalyzingthis type of system? 4. How is user privacy maintainable? 5. What is the role of trust? Thesequestionswerediscussedduringtheconferencestimulatedbytwokeynote and three invited speeches. Two of the speakers have taken the opportunity to present their ideas in this book. Organic computing is a research area initiated by the special interest group ARCS of the German computer societies (GI and ITG) that are responsible for the organization of the ARCS conference series. Future ARCS conferences will thereforecontinuetogiveaplatformtorevolutionaryideasforanewgeneration of organic computing systems. The great interest of the research community in the research field of this conference is expressed in a large number of submitted papers. Altogether, we received 174 papers, 32 of them were accepted and are presented in this book. We were especially pleased by the wide range of countries represented at the conference. We thank all the members of the Program Committee, who did a great job. Many additional reviewers supported us in selecting the best papers. We thank all reviewers for their elaborated reviews which greatly helped the authorstofurtherimprovetheirpapers.Readerswillappreciatethiseffortyield- ing a book with high quality. The organization of this conference was done at two different locations. Or- ganizational tasks were performed at the University of Frankfurt a.M., while the work on the program was done at the University of Passau. We thank all staff members for their excellent work making this conference a success. Special thanksfortheirexcellentworkgoto:MarkusDamm,DianaFirnges,JanHaase, JohannesHerr,WilhelmHeupke,JoachimHo¨hne,AlexanderHofmann,Andreas Hofmann, Eva Kapfer, Anita Plattner, Franz Rautmann, Ru¨diger Schroll. March 2006 Werner Grass Bernhard Sick Klaus Waldschmidt Organization ARCS2006wasjointly organizedby GI(GermanInformaticsSociety) andITG (Information Technology Society). Executive Committee General Chair: Klaus Waldschmidt (University of Frankfurt, Germany) ProgramChair: WernerGrass(UniversityofPassau,Germany) Workshop and Tutorial Chair: Wolfgang Karl (University of Karlsruhe, Germany) Program Committee Nader Bagherzadeh University of California, Irvine, USA Ju¨rgen Becker University of Karlsruhe, Germany Michael Beigl University of Karlsruhe, Germany Riccardo Bettati Texas A&M University, College Station, USA Uwe Brinkschulte University of Karlsruhe, Germany Hermann De Meer University of Passau, Germany Francois Dolivo IBM, Zurich Research Laboratory,Switzerland Stefan Dulman Ambient Systems, Enschede, The Netherlands Marc Duranton Philips Research, Eindhoven, The Netherlands Alois Ferscha University of Linz, Austria Marisol Garcia-Valls University Carlos III, Madrid, Spain Jean-Luc Gaudiot University of California, Irvine, USA Werner Grass University of Passau, Germany Paul Havinga University of Twente, The Netherlands Oliver Heckmann Technical University of Darmstadt, Germany Wolfgang Karl University of Karlsruhe, Germany Rudolf Kober Siemens AG, Munich, Germany Spyros Lalis University of Thessaly, Greece Paul Lukowicz University for Health Sciences, Medical Informatics and Technology, Austria Erik Maehle University of Lu¨beck, Germany Tom Martin Virginia Tech, Blacksburg, USA Christian Mu¨ller-Schloer University of Hanover, Germany Timothy M. Pinkston UniversityofSouthernCalifornia,LosAngeles,USA Ichiro Satoh National Institute of Informatics, Tokyo, Japan Hartmut Schmeck University of Karlsruhe, Germany Martin Schulz Lawrence Livermore National Laboratory, Livermore, USA Karsten Schwan Georgia Institute of Technology, Atlanta, USA VIII Organization Bernhard Sick University of Passau, Germany Peter Steenkiste Carnegie Mellon University, Pittsburgh, USA Roy Sterritt University of Ulster at Jordanstown, UK Ju¨rgen Teich University of Erlangen-Nuremberg,Germany Yoshito Tobe Tokyo Denki University, Japan Kishor Trivedi Duke University, Durham, USA Rich Uhlig Intel MicroprocessorResearch Lab, USA Theo Ungerer University of Augsburg, Germany Klaus Waldschmidt University of Frankfurt, Germany Ralph Welge University of Lu¨neburg, Germany Sami Yehia ARM Research, Cambridge, UK Additional Referees C. Albrecht C. Hochberger F. Picioroaga F. Bagci C. Hoertnagl A. Pietzowski J. H. Bahn A. Hofmann T. Pionteck P. Basanta-Val T. Hofmeijer G. Rey M. Berger R. Holzer F. Rochner G. Brancovici C. Holzmann S. Roos J. Brehm I. Iliadis Y. Sazeides I. Buhan C. Ilioudis A. Schill C. Cachin G. Karjoth T. Scho¨ler J. Camenisch S. Karlsson W. Schro¨der-Preikschat Z. Chamski T. Kirste P. Scotton S. Cho D. Koblitz T. Smaoui V. Desmet R. Koch P. Sobe O. Durmaz Incel W. P. Kowalk P. Soulard S. Eilers M. Litza M. Stolze I. Estevez-Ayres T. Loukopoulos D. Tavangarian L. Evers N. Luttenberger P. Trancoso F. Fuchs G. Mahmoudi J. Trescher R. Gemesi M. Marin-Perianu W. Trumler M. Go¨nne R. Marin-Perianu V. Turau M. Graf N. Meratnia E. Van Herreweghen A. Gro¨ßlinger M. Mnif S. Voigt K.-E. Grosspietsch F. M¨osch S. Wang C. Gruber M. Mu¨hlha¨user E. Zehendner A. Hatanaka K. Muthukrishnan A. Zell A. Hazem El-Mahdy F. Neeser Y. Zhu E. A. Heinz E. O¨zer J. Henkel H. Pals WealsothankalladditionalrefereeswhosenamesareunknowntotheExecutive Committee. Table of Contents Invited and Keynote Papers Life-Inspired Systems and Their Quality-Driven Design Lech J´o´zwiak .................................................. 1 The Robustness of Resource Allocations in Parallel and Distributed Computing Systems Vladimir Shestak, Howard Jay Siegel, Anthony A. Maciejewski, Shoukat Ali ................................................... 17 Pervasive Computing FingerMouse – A Button Size Visual Hand Tracking and Segmentation Device Patrick de la Hamette, Gerhard Tro¨ster .......................... 31 An Ad-Hoc Wireless Network Architecture for Face-to-Face Mobile Collaborative Applications Gustavo Zurita, Miguel Nussbaum................................ 42 BackgroundData Acquisition and Carrying: The BlueDACS Project Thomas Wieland, Martin Fenne, Benjamin Sto¨cker ................ 56 Prototypical Implementation of Location-Aware Services Based on Super-Distributed RFID Tags Ju¨rgen Bohn .................................................. 69 Combined Resource and Context Model for QoS-Aware Mobile Middleware Sten Lundesgaard Amundsen, Frank Eliassen ...................... 84 Distributed Modular Toolbox for Multi-modal Context Recognition David Bannach, Kai Kunze, Paul Lukowicz, Oliver Amft ........... 99 Memory Systems Dynamic Dictionary-BasedData Compression for Level-1 Caches Georgios Keramidas, Konstantinos Aisopos, Stefanos Kaxiras............................................... 114 X Table of Contents A Case for Dual-Mapping One-Way Caches Arul Sandeep Gade, Yul Chu .................................... 130 Cache Write-Back Schemes for Embedded Destructive-Read DRAM Haakon Dybdahl, Marius Grannæs, Lasse Natvig ................... 145 A Processor Architecture with Effective Memory System for Sort-Last Parallel Rendering Woo-Chan Park, Duk-Ki Yoon, Kil-Whan Lee, Il-San Kim, Kyung-Su Kim, Won-Jong Lee, Tack-Don Han, Sung-Bong Yang .... 160 Architectures Controller Synthesis for Mapping Partitioned Programs on Array Architectures Hritam Dutta, Frank Hannig, Ju¨rgen Teich........................ 176 M2E: A Multiple-Input, Multiple-Output Function Extension for RISC-Based Extensible Processors Xiaoyong Chen, Douglas L. Maskell .............................. 191 An Operating System Infrastructure for Fault-Tolerant Reconfigurable Networks Dirk Koch, Thilo Streichert, Steffen Dittrich, Christian Strengert, Christian D. Haubelt, Ju¨rgen Teich............................... 202 Architectural Tradeoffs in Wearable Systems Nagendra Bhargava Bharatula, Urs Anliker, Paul Lukowicz, Gerhard Tr¨oster ............................................... 217 Multiprocessing Do Trace Cache, Value Prediction and Prefetching Improve SMT Throughput? Chen-Yong Cher, Il Park, T.N. VijayKumar ...................... 232 Scalable and Partitionable Asynchronous Arbiter for Micro-threaded Chip Multiprocessors Nabil Hasasneh, Ian Bell, Chris Jesshope ......................... 252 GigaNetIC – A Scalable Embedded On-Chip Multiprocessor Architecture for Network Applications Jo¨rg-Christian Niemann, Christoph Puttmann, Mario Porrmann, Ulrich Ru¨ckert ................................................ 268 Table of Contents XI Energy Efficient Design Efficient System-on-Chip Energy Management with a Segmented Bloom Filter Mrinmoy Ghosh, Emre O¨zer, Stuart Biles, Hsien-Hsin S. Lee........ 283 Estimating Energy Consumption for an MPSoC Architectural Exploration Rabie Ben Atitallah, Smail Niar, Alain Greiner, Samy Meftali, Jean Luc Dekeyser ............................................. 298 An Energy Consumption Model for an Embedded Java Virtual Machine S´ebastien Lafond, Johan Lilius .................................. 311 Power Awareness PASCOM: Power Model for Supercomputers Arrvindh Shriraman, Nagarajan Venkateswaran, Niranjan Soundararajan ........................................ 326 Power-AwareCollective Tree Exploration Miroslaw Dynia, Miroslaw Korzeniowski, Christian Schindelhauer .... 341 Biologically-InspiredOptimizationofCircuitPerformanceandLeakage: A Comparative Study Ralf Salomon, Frank Sill ........................................ 352 Network Protocols A Synchronous Multicast Application for Asymmetric Intra-campus Networks: Definition, Analysis and Evaluation Pilar Manzanares-Lopez, Juan Carlos Sanchez-Aarnoutse, Josemaria Malgosa-Sanahuja, Joan Garcia-Haro ................... 367 A Real-Time MAC Protocol for Wireless Sensor Networks: Virtual TDMA for Sensors (VTS) Esteban Egea-L´opez, Javier Vales-Alonso, Alejandro S. Mart´ınez-Sala, Joan Garc´ıa-Haro, Pablo Pav´on-Marin˜o, M. Victoria Bueno-Delgado.................. 382 An Effective Video Streaming Method for Video on Demand Services in Vertical Handoff Jae-Won Kim, Hye-Soo Kim, Jae-Woong Yun, Sung-Jea Ko ........ 397