Part 1: Multicore and Many-Co
Table of Contents
Preface xxix Acknowledgments xxxvii
List of Figures xxxix
List of Tables li
List of Contributors lv
PART 1 MULTICORE AND MANY-CORE (MC) SYSTEMS-ON-CHIP
1 A RECONFIGURABLE ON-CHIP INTERCONNECTION NETWORK FOR LARGE MULTICORE SYSTEMS 3
Mehdi Modarressi and Hamid Sarbazi-Azad
1.1 Introduction 4
1.2 Topology and Reconfiguration 8
1.3 The Proposed NoC Architecture 9
1.4 Energy and Performance-Aware Mapping 14
1.5 Experimental Results 19
1.6 Conclusion 25
2 COMPILERS, TECHNIQUES, AND TOOLS FOR SUPPORTING PROGRAMMING HETEROGENEOUS MANY/MULTICORE SYSTEMS 31
Pasquale Cantiello, Beniamino Di Martino, and Francesco Moscato
2.1 Introduction 32
2.2 Programming Models and Tools for Many/Multicore 32
2.3 Compilers and Support Tools 42
2.4 CALuMET: A Tool for Supporting Software Parallelization 45
2.5 Conclusion 49
3 A MULTITHREADED BRANCH-AND-BOUND ALGORITHM FOR SOLVING THE FLOW-SHOP PROBLEM ON A MULTICORE ENVIRONMENT 53
Mohand Mezmaz, Nouredine Melab, and Daniel Tuyttens
3.1 Introduction 54
3.2 Flow-Shop Scheduling Problem 55
3.3 Parallel Branch-and-Bound Algorithms 56
3.4 A Multithreaded Branch-and-Bound 58
3.5 The Proposed Multithreaded B&B 60
3.6 Experiments and Results 63
3.7 Conclusion 68
PART 2 PERVASIVE/UBIQUITOUS COMPUTING AND PEER-TO-PEER SYSTEMS 4 LARGE-SCALE P2P-INSPIRED PROBLEM-SOLVING: A FORMAL AND EXPERIMENTAL STUDY 73
Mathieu Djama¨ý, Bilel Derbel, and Nouredine Melab
4.1 Introduction 74
4.2 Background 77
4.3 A Pure Peer-to-Peer B&B Approach 80
4.4 Complexity Issues 87
4.5 Experimental Results 90
4.6 Conclusion 99
Acknowledgment 99
5 DATA DISTRIBUTION MANAGEMENT 103
Azzedine Boukerche and Yunfeng Gu
5.1 Addressing DDM in Different Network Environments 104
5.2 DDM in P2P Overlay Networks 106
5.3 DDM in Cluster-Based Network Environments 111
6 MIDDLEWARE SUPPORT FOR CONTEXT HANDLING AND INTEGRATION IN UBIQUITOUS COMPUTING 123
Frederico Lopes, Paulo F. Pires, Flávia C. Delicato, Thais Batista, and Luci Pirmez
6.1 Introduction 124
6.2 Ubiquitous Computing 126
6.3 Middleware for Ubiquitous Computing 128
6.4 A Solution to Integrating Context Provision Middleware for Ubiquitous Computing 133
6.5 Conclusion 142
PART 3 WIRELESS/MOBILE NETWORKS
7 CHALLENGES IN THE USE OF WIRELESS SENSOR NETWORKS FOR MONITORING THE HEALTH OF CIVIL STRUCTURES 147
Flávia C. Delicato, Igor L. dos Santos, Luci Pirmez, Paulo F. Pires, and Claudio M. de Farias
7.1 Introduction 148
7.2 Structural Health Monitoring 150
7.3 Wireless Sensor Networks 155
7.4 Applying Wireless Sensor Networks for Structural Health Monitoring 157
7.5 Conclusion 163
8 MOBILITY EFFECTS IN WIRELESS MOBILE NETWORKS 167
Abbas Nayebi and Hamid Sarbazi-Azad
8.1 Introduction 167
8.2 The Effect of Node Mobility on Wireless Links 168
8.3 The Effect of Node Mobility on Network Topology 172
8.4 Conclusion 177
9 ANALYTICAL MODEL OF TIME-CRITICAL WIRELESS SENSOR NETWORK: THEORY AND EVALUATION 183
Kambiz Mizanian and Amir Hossein Jahangir
9.1 Introduction 184
9.2 Real-Time Wireless Sensor Network: An Overview 185
9.3 Real-Time Degree 188
9.4 Reliable Real-Time Degree 195
9.5 Model Validation 197
9.6 Conclusion 199
10 MULTICAST TRANSPORT PROTOCOLS FOR LARGE-SCALE DISTRIBUTED COLLABORATIVE ENVIRONMENTS 203
Haifa Raja Maamar and Azzedine Boukerche
10.1 Introduction 204
10.2 Definition and Features 204
10.3 Classification of Multicast Protocols 207
10.4 Conclusion 216
11 NATURE-INSPIRED COMPUTING FOR AUTONOMIC WIRELESS SENSOR NETWORKS 219
Wei Li, Javid Taheri, Albert Y. Zomaya, Franciszek Seredynski, and Bjorn Landfeldt
11.1 Introduction 220
11.2 Autonomic WSNs 222
11.3 Principles of Nature-Inspired Computing 224
11.4 Cellular Automata 226
11.5 Swarm Intelligence 228
11.6 Artificial Immune Systems 233
11.7 Evolutionary Computing 238
11.8 Molecular Biology 242
11.9 Bio-Networking Architecture 243
11.10 Conclusion 244
PART 4 GRID AND CLOUD COMPUTING
12 SMART RPC-BASED COMPUTING IN GRIDS AND ON CLOUDS 257
Thomas Brady, Oleg Girko, and Alexey Lastovetsky
12.1 Introduction 258
12.2 SmartGridRPC and SmartGridSolve 266
12.3 Making SmartGridSolve Smarter 277
12.4 Smart RPC-Based Computing on Clouds: Adaptation of SmartGridRPC and SmartGridSolve to Cloud Computing 282
13 PROFIT-MAXIMIZING RESOURCE ALLOCATION FOR MULTITIER CLOUD COMPUTING SYSTEMS UNDER SERVICE LEVEL AGREEMENTS 291
Hadi Goudarzi and Massoud Pedram
13.1 Introduction 292
13.2 Review of Datacenter Power Management Techniques 294
13.3 Review of Datacenter Performance Management Techniques 296
13.4 System Model of a Multitier Application Placement Problem 298
13.5 Profit Maximization in a Hosting Datacenter 303
13.6 Simulation Results 310
13.7 Conclusion 314
14 MARKET-ORIENTED CLOUD COMPUTING AND THE CLOUDBUS TOOLKIT 319
Rajkumar Buyya, Suraj Pandey, and Christian Vecchiola
14.1 Introduction 320
14.2 Cloud Computing 322
14.3 Cloudbus: Vision and Architecture 338
14.4 Cloudbus and Clouds Lab Technologies 340
14.5 Experimental Results 345
14.6 Related Technologies, Integration, and Deployment 350
14.7 Conclusion 351
15 A CLOUD BROKER ARCHITECTURE FOR MULTICLOUD ENVIRONMENTS 359
Jose Luis Lucas-Simarro, Iñigo San Aniceto, Rafael Moreno-Vozmediano, Ruben S. Montero, and Ignacio M. Llorente
15.1 Introduction 360
15.2 State of the Art on Cloud Brokering 361
15.3 Challenges of Cloud Brokering 363
15.4 Proposal of a Broker Architecture for Multicloud Environments 364
15.5 Scheduling Policies for Efficient Cloud Brokering 367
15.6 Results 369
15.7 Conclusion 373
16 ENERGY-EFFICIENT RESOURCE UTILIZATION IN CLOUD COMPUTING 377
Giorgio L. Valentini, Samee U. Khan, and Pascal Bouvry
16.1 Introduction 378
16.2 Related Work 380
16.3 Energy-Efficient Utilization of Resources in Cloud Computing Systems 381
16.4 Complementarity Approach 386
16.5 Simulation Results 395
16.6 Discussion of Results 402
16.7 Conclusion 404
17 SEMANTICS-BASED RESOURCE DISCOVERY IN LARGE-SCALE GRIDS 409
Juan Li, Samee U. Khan, and Nasir Ghani
17.1 Introduction 410
17.2 Related Work 411
17.3 Virtual Organization Formation 412
17.4 Semantics-Based Resource Discovery in Virtual Organizations 417
17.5 Prototype Implementation and Evaluation 421
17.6 Conclusion 427
18 GAME-BASED MODELS OF GRID USER’S DECISIONS IN SECURITY-AWARE SCHEDULING 431
Joanna Kolodziej, Samee U. Khan, Lizhe Wang, and Dan Chen
18.1 Introduction 432
18.2 Security-Aware Scheduling Problems in Computational Grids 433
18.3 Game Models in Security-Aware Grid Scheduling 441
18.4 Case Study: Approximating the Equilibrium States of the End Users’ Symmetric Game Using the Genetic Metaheuristics 447
18.5 Conclusion 460
19 ADDRESSING OPEN ISSUES ON PERFORMANCE EVALUATION IN CLOUD COMPUTING 463
Beniamino Di Martino, Massimo Ficco, Massimiliano Rak,and Salvatore Venticinque
19.1 Introduction 464
19.2 Benchmarking Approaches 465
19.3 Monitoring in Cloud Computing 468
19.4 Attack Countermeasures in Cloud Computing 474
19.5 Conclusion 480
20 BROKER-MEDIATED CLOUD-AGGREGATION MECHANISM USING MARKOVIAN QUEUES FOR SCHEDULING BAG-OF-TASKS (BOT) APPLICATIONS 485
Ganesh Neelakanta Iyer and Bharadwaj Veeravalli
20.1 Introduction 486
20.2 Literature Review and Contributions 487
20.3 Problem Setting and Notations 488
20.4 Proposed Cloud Aggregation Mechanism 489
20.5 Performance Evaluation and Discussions 494
20.6 Discussions 497
20.7 Conclusion 498
21 ON THE DESIGN OF A BUDGET-CONSCIOUS ADAPTIVE SCHEDULER FOR HANDLING LARGE-SCALE MANY-TASK WORKFLOW APPLICATIONS IN CLOUDS 503
Bharadwaj Veeravalli, Lingfang Zeng, and Xiaorong Li
21.1 Introduction 504
21.2 Related Work and Motivation 505
21.3 System Model and Problem Setting 506
21.4 Proposed Scheduling Algorithm 512
21.5 Performance Evaluation and Results 516
21.6 Conclusion 522
22 VIRTUALIZED ENVIRONMENT ISSUES IN THE CONTEXT OF A SCIENTIFIC PRIVATE CLOUD 527
Bruno Schulze, Henrique de Medeiros Klˆoh, Matheus Bousquet Bandini, Antonio Roberto Mury, Daniel Massami Muniz Yokoyama, Victor Dias de Oliveira, F´abio Andr´e Machado Porto, and Giacomo Victor McEvoy Valenzano
22.1 Introduction 528
22.2 Related Works 528
22.3 Methodology 531
22.4 Experiments 533
22.5 Conclusion 544
22.6 Glossary 546
PART 5 OTHER TOPICS RELATED TO NETWORK-CENTRIC COMPUTING AND ITS APPLICATIONS
23 IN-ADVANCE BANDWIDTH SCHEDULING IN e-SCIENCE NETWORKS 551
Yan Li, Eunsung Jung, Sanjay Ranka, Nageswara S. Rao, and Sartaj Sahni
23.1 Introduction 552
23.2 Temporal Network Model 554
23.3 Single-Path Scheduling 556
23.4 Multiple-Path Scheduling 570
23.5 Conclusion 587
24 ROUTING AND WAVELENGTH ASSIGNMENT IN OPTICAL NETWORKS 591
Yan Li, Sanjay Ranka, and Sartaj Sahni
24.1 Introduction 592
24.2 Scheduling in Full-Wavelength Conversion Network 593
24.3 Scheduling in Sparse Wavelength Conversion Network 603
25 COMPUTATIONAL GRAPH ANALYTICS FOR MASSIVE STREAMING DATA 619
David Ediger, Jason Riedy, David A. Bader, and Henning Meyerhenke
25.1 Introduction 620
25.2 STINGER: A General-Purpose Data Structure for Dynamic Graphs 622
25.3 Algorithm for Updating Clustering Coefficients 625
25.4 Tracking Connected Components in Scale-Free Graphs 628
25.5 Implementation 632
25.6 Experimental Results 634
25.7 Related Work 643
25.8 Conclusion 644
26 KNOWLEDGE MANAGEMENT FOR FAULT-TOLERANT WATER DISTRIBUTION 649
Jing Lin, Ali Hurson, and Sahra Sedigh
26.1 Introduction 650
26.2 Related Work 652
26.3 Agent-Based Model for WDN Operation 653
26.4 Classes in WDN Ontology Framework 656
26.5 Automated Failure Classification and Mitigation 659
26.6 Validation of Automated Failure Mitigation 668
26.7 Conclusion 674
Acknowledgment 675
References 675
Index 679
