Large Scale Network-Centric Distributed Systems E-Book
116,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: Wiley Series on Parallel and Distributed Computing
- Sprache: Englisch
A highly accessible reference offering a broad range of topics and insights on large scale network-centric distributed systems
Evolving from the fields of high-performance computing and networking, large scale network-centric distributed systems continues to grow as one of the most important topics in computing and communication and many interdisciplinary areas. Dealing with both wired and wireless networks, this book focuses on the design and performance issues of such systems.
Large Scale Network-Centric Distributed Systems provides in-depth coverage ranging from ground-level hardware issues (such as buffer organization, router delay, and flow control) to the high-level issues immediately concerning application or system users (including parallel programming, middleware, and OS support for such computing systems). Arranged in five parts, it explains and analyzes complex topics to an unprecedented degree:
- Part 1: Multicore and Many-Core (Mc) Systems-on-Chip
- Part 2: Pervasive/Ubiquitous Computing and Peer-to-Peer Systems
- Part 3: Wireless/Mobile Networks
- Part 4: Grid and Cloud Computing
- Part 5: Other Topics Related to Network-Centric Computing and Its Applications
Large Scale Network-Centric Distributed Systems is an incredibly useful resource for practitioners, postgraduate students, postdocs, and researchers.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 1289
Veröffentlichungsjahr: 2013
Ähnliche
Contents
Cover
Wiley Series on Parallel and Distributed Computing
Title Page
Copyright
Dedication
Preface
Acknowledgments
List of Figures
List of Tables
List of Contributors
Part 1: Multicore and Many-Core (MC) Systems-On-Chip
Chapter 1: A Reconfigurable On-Chip Interconnection Network for Large Multicore Systems
1.1 Introduction
1.2 Topology and Reconfiguration
1.3 The proposed NoC Architecture
1.4 Energy and Performance-Aware Mapping
1.5 Experimental Results
1.6 Conclusion
References
Chapter 2: Compilers, Techniques, and Tools for Supporting Programming Heterogeneous Many/Multicore Systems
2.1 Introduction
2.2 Programming Models and Tools for Many/Multicore
2.3 Compilers and Support Tools
2.4 CALuMET: A Tool for Supporting Software Parallelization
2.5 Conclusion
References
Chapter 3: A Multithreaded Branch-and-Bound Algorithm for Solving the Flow-Shop Problem on a Multicore Environment
3.1 Introduction
3.2 Flow-Shop Scheduling Problem
3.3 Parallel Branch-and-Bound Algorithms
3.4 A Multithreaded Branch-and-Bound
3.5 The Proposed Multithreaded B&B
3.6 Experiments and Results
3.7 Conclusion
References
Part 2: Pervasive/Ubiquitous Computing and Peer-To-Peer Systems
Chapter 4: Large-Scale P2P-Inspired Problem-Solving: A Formal and Experimental Study
4.1 Introduction
4.2 Background
4.3 A Pure Peer-to-Peer B&B Approach
4.4 Complexity Issues
4.5 Experimental Results
4.6 Conclusion
Acknowledgment
References
Chapter 5: Data Distribution Management
5.1 Addressing DDM in Different Network Environments
5.2 DDM in P2P Overlay Networks
5.3 DDM in Cluster-Based Network Environments
References
Chapter 6: Middleware Support for Context Handling and Integration in Ubiquitous Computing
6.1 Introduction
6.2 Ubiquitous Computing
6.3 Middleware for Ubiquitous Computing
6.4 A Solution to Integrating Context Provision Middleware for Ubiquitous Computing
6.5 Conclusion
Acknowledgments
References
Part 3: Wireless/Mobile Networks
Chapter 7: Challenges in the Use of Wireless Sensor Networks for Monitoring the Health of Civil Structures
7.1 Introduction
7.2 Structural Health Monitoring
7.3 Wireless Sensor Networks
7.4 Applying Wireless Sensor Networks for Structural Health Monitoring
7.5 Conclusion
Acknowledgments
References
Chapter 8: Mobility Effects in Wireless Mobile Networks
8.1 Introduction
8.2 The Effect of Node Mobility on Wireless Links
8.3 The Effect of Node Mobility on Network Topology
8.4 Conclusion
References
Chapter 9: Analytical Model of Time-Critical Wireless Sensor Network: Theory and Evaluation
9.1 Introduction
9.2 Real-Time Wireless Sensor Network: An Overview
9.3 Real-Time Degree
9.4 Reliable Real-Time Degree
9.5 Model Validation
9.6 Conclusion
References
Chapter 10: Multicast Transport Protocols for Large-Scale Distributed Collaborative Environments
10.1 Introduction
10.2 Definition and Features
10.3 Classification of Multicast Protocols
10.4 Conclusion
References
Chapter 11: Nature-Inspired Computing for Autonomic Wireless Sensor Networks
11.1 Introduction
11.2 Autonomic WSNs
11.3 Principles of Nature-Inspired Computing
11.4 Cellular Automata
11.5 Swarm Intelligence
11.6 Artificial Immune Systems
11.7 Evolutionary Computing
11.8 Molecular Biology
11.9 Bio-networking Architecture
11.10 Conclusion
References
Part 4: Grid and Cloud Computing
Chapter 12: Smart RPC-Based Computing in Grids and on Clouds
12.1 Introduction
12.2 SmartGridRPC and SmartGridSolve
12.3 Making SmartGridSolve Smarter
12.4 Smart RPC-Based Computing on Clouds: Adaptation of SmartGridRPC and SmartGridSolve to Cloud Computing
Acknowledgment
References
Chapter 13: Profit-Maximizing Resource Allocation for Multitier Cloud Computing Systems under Service Level Agreements
13.1 Introduction
13.2 Review of Datacenter Power Management Techniques
13.3 Review of Datacenter Performance Management Techniques
13.4 System Model of a Multitier Application Placement Problem
13.5 Profit Maximization in a Hosting Datacenter
13.6 Simulation Results
13.7 Conclusion
References
Chapter 14: Market-Oriented Cloud Computing and the Cloudbus Toolkit
14.1 Introduction
14.2 Cloud Computing
14.3 Cloudbus: Vision and Architecture
14.4 Cloudbus and Clouds Lab Technologies
14.5 Experimental Results
14.6 Related Technologies, Integration, and Deployment
14.7 Conclusion
Acknowledgments
References
Chapter 15: A Cloud Broker Architecture for MultiCloud Environments
15.1 Introduction
15.2 State of the Art on Cloud Brokering
15.3 Challenges of Cloud Brokering
15.4 Proposal of a Broker Architecture for Multicloud Environments
15.5 Scheduling Policies for Efficient Cloud Brokering
15.6 Results
15.7 Conclusion
Acknowledgments
References
Chapter 16: Energy-Efficient Resource Utilization in Cloud Computing
16.1 Introduction
16.2 Related Work
16.3 Energy-Efficient Utilization of Resources in Cloud Computing Systems
16.4 Complementarity Approach
16.5 Simulation Results
16.6 Discussion of Results
16.7 Conclusion
References
Chapter 17: Semantics-Based Resource Discovery in Large-Scale Grids
17.1 Introduction
17.2 Related Work
17.3 Virtual Organization Formation
17.4 Semantics-Based Resource Discovery in Virtual Organizations
17.5 Prototype Implementation and Evaluation
17.6 Conclusion
References
Chapter 18: Game-Based Models of Grid User's Decisions in Security-Aware Scheduling
18.1 Introduction
18.2 Security-Aware Scheduling Problems in Computational Grids
18.3 Game Models in Security-Aware Grid Scheduling
18.4 Case Study: Approximating the Equilibrium States of the End Users' Symmetric Game Using the Genetic Metaheuristics
18.5 Conclusion
References
Chapter 19: Addressing Open Issues on Performance Evaluation in Cloud Computing
19.1 Introduction
19.2 Benchmarking Approaches
19.3 Monitoring in Cloud Computing
19.4 Attack Countermeasures in Cloud Computing
19.5 Conclusion
References
Chapter 20: Broker-Mediated Cloud-Aggregation Mechanism Using Markovian Queues for Scheduling Bag-of-Tasks (BoT) Applications
20.1 Introduction
20.2 Literature Review and Contributions
20.3 Problem Setting and Notations
20.4 Proposed Cloud Aggregation Mechanism
20.5 Performance Evaluation and Discussions
20.6 Discussions
20.7 Conclusion
References
Chapter 21: On the Design of a Budget-Conscious Adaptive Scheduler for Handling Large-Scale Many-Task Workflow Applications in Clouds
21.1 Introduction
21.2 Related Work and Motivation
21.3 System Model and Problem Setting
21.4 Proposed Scheduling Algorithm
21.5 Performance Evaluation and Results
21.6 Conclusion
References
Chapter 22: Virtualized Environment Issues in the Context of a Scientific Private Cloud
22.1 Introduction
22.2 Related Works
22.3 Methodology
22.4 Experiments
22.5 Conclusion
22.6 Glossary
Acknowledgments
References
Part 5: Other Topics Related to Network-Centric Computing and Its Applications
Chapter 23: In-Advance Bandwidth Scheduling in e-Science Networks
23.1 Introduction
23.2 Temporal Network Model
23.3 Single-Path Scheduling
23.4 Multiple-Path Scheduling
23.5 Conclusion
Acknowledgment
References
Chapter 24: Routing and Wavelength Assignment in Optical Networks
24.1 Introduction
24.2 Scheduling in Full-Wavelength Conversion Network
24.3 Scheduling in Sparse Wavelength Conversion Network
Acknowledgment
References
Chapter 25: Computational Graph Analytics for Massive Streaming Data
25.1 Introduction
25.2 STINGER: A General-Purpose Data Structure for Dynamic Graphs
25.3 Algorithm for Updating Clustering Coefficients
25.4 Tracking Connected Components in Scale-Free Graphs
25.5 Implementation
25.6 Experimental Results
25.7 Related Work
25.8 Conclusion
Acknowledgments
References
Chapter 26: Knowledge Management for Fault-Tolerant Water Distribution
26.1 Introduction
26.2 Related Work
26.3 Agent-Based Model for WDN Operation
26.4 Classes in WDN Ontology Framework
26.5 Automated Failure Classification and Mitigation
26.6 Validation of Automated Failure Mitigation
26.7 Conclusion
Acknowledgments
References
Index
Cover Design: Wiley
Cover Image: ©iStockphoto.com/elly99
Copyright 2014 by John Wiley & Sons, Inc. All rights reserved.
Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Large scale network-centric distributed systems / edited by Hamid Sarbazi-Azad, Albert Y. Zomaya.
pages cm
ISBN 978-0-470-93688-7 (pbk.)
1. Electronic data processing–Distributed processing. I. Sarbazi-Azad, Hamid. II. Zomaya, Albert Y.
QA76.9.D5L373 2013
004'.36–dc23
2012047719
To our families for their help, support, and patience.
Hamid Sarbazi-Azad and Albert Zomaya
Preface
On one hand, the cost of computing resources has decreased rapidly, and on the other hand, the availability of them has increased swiftly in recent years. In the meanwhile, a great amount of intensive applications with greater performance and fault tolerance requirements has emerged. These trends collectively have made centralized designs of the information systems less desirable and distributed systems more widespread in several domains, despite them having more technical difficulties. Obviously, it is the network that sticks the components of such systems together, and it has become apparent that the effectiveness of the operation of the network together with the way it is exploited, primarily determines the quality of the cooperation of those components. Today, network centric computing systems is a subject of interest in the whole extent to which distributed systems operate, from those which are composed of multiple cores on a single chip to those which take advantage of a great number of computers connected together in order to create grids, clouds, and other network-based distributed systems.
In this book, a range of relevant topics in the scope of Large Scale Network-Centric Distributed Systems is presented, which covers a selection of its many aspects. It is composed of five parts, each of which includes different chapters authored by the researchers in the field and selected based on a peer-review. A brief summary of the chapters is provided below to give an initiatory sight of the scope of the book.
Part 1 is dedicated to network-based systems-on-chip (SoC) comprising multiple cores. The number of cores on a chip has been growing in recent years and according to ITRS projection, chips with several hundred to thousand cores are on their way. These cores are usually interconnected via a network for data interchange between the different tasks, programs, and threads running on different cores. Studying different issues related to multicore SoCs, from hardware and architectural techniques to software solutions, is of utmost importance. This part includes three chapters.
Chapter 1 introduces a reconfigurable network-on-chip (NoC) which can adapt network topology to the communication requirements of the applications running on different cores. Network topology is the most critical part of an NoC and mainly determines its performance. Having a network with a dynamic topology to adapt the communication requirements of the applications can effectively improve performance and reduce energy consumption. Design issues and experimental evaluation of the proposed reconfigurable architecture is detailed in this chapter.
Chapter 2 briefly reviews different programming models for current multicore systems (espcially GPUs (Graphics Processing Units) which have gained great importance for building large supercomputers) and the state of the art on compilers and support tools helping programmers both in developing and porting codes for multicore systems with an emphasis on automatic parallelization compilers, techniques and tools that do source-to-source transformation of sequential code into parallel. This chapter introduces a tool developed by the authors, to do static analysis on source code in order to represent it along with knowledge extracted from it. The tool integrates an algorithmic recognizer to find instances of known algorithms, and a transformer to automatically transform sequential code into a parallel version by using libraries, so that it could be used in GPUs.
In Chapter 3, authors propose a multi-threaded branch-and-bound (B&B) approach to solve the flow-shop scheduling problem on a multi-core system. Several exact resolution methods used in combinatorial optimization are B&B like algorithms. The proposed approach is implemented using the POSIX Threads programming model. The experiments demonstrate that the use of the total available power in a multi-core CPU does not mean that the maximum speedup is achieved. These experiments show that a multi-threaded B&B approach must take into account the characteristics of its hardware and software environment, such as the size of the random-access memory.
Ubiquitous computing (UC) or pervasive computing is a paradigm where machines fit the human environment instead of forcing humans to enter theirs. Contemporary human-computer interaction models, whether command-line, menu-driven, or GUI (Graphical User Interface)-based, are inappropriate and inadequate to the ubiquitous case. This suggests that the natural interaction paradigm appropriate for a fully robust UC has yet to emerge, although there is also recognition in the field that in many ways we are already living in an ubicomp world. Contemporary devices that lend some support to this latter idea include mobile phones, digital audio players, radio-frequency identification tags, GPS, and interactive whiteboards. Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the application. They are said to form a P2P network of nodes. Peers make a portion of their resources, such as processing power, disk storage or network bandwidth, directly available to other network participants, without the need for central coordination by servers or stable hosts. Peers are both suppliers and consumers of resources, in contrast to the traditional client–server model where the consumption and supply of resources is always divided. Part 2 deals with some important problems in pervasive/ubiquitous computing and peer-to-peer systems. It comprises of three chapters.
In Chapter 4, a new P2P approach is introduced which can handle a huge amount of computational resources in a fully distributed way; that is without the need of any centralized coordinator. The state-of-the-art large scale approach for solving NP-hard permutation-based problems using parallel B&B techniques is based on a Master-Slave model which is known to be limited in terms of scalability. Authors present simple and efficient fully distributed algorithms dealing with major parallel B&B issues such as work sharing, dynamic load balancing and termination detection. The proposed P2P approach has a scalability which is exponentially better in theory compared to the Master-Slave technique, while having a negligible communication overhead in a worst case-scenario, namely poly-logarithmic.
In addition, a more detailed analysis of performance of the proposed approach is realized through studying its different execution phases and its behavior when solving some instances of the Flow-Shop Scheduling Problem from scratch, a well-known permutation-based problem in the field of Combinatorial Optimization.
In Chapter 5, Data Distribution Management (DDM) is addressed in two different network environments: P2P overlay networks and cluster-based networks. Although DDM provides the same data indexing service in both distributed network environments, it serves upper layer applications for very different purposes, and is supported by underlying networks with distinctive infrastructures. In P2P overlay networks, peers share part of their resources.
They might have different capacities to share the load, some might join or leave the system, or even fail, and the connectivity between them is unstable. DDM in P2P overlay networks is more feasible for massive data sharing systems or massively parallel computing. On the other hand, all peers in a cluster network are dedicated resources of the distributed environment. The cluster network might have very limited size, but the status of a peer is highly reliable, and the connectivity is always stable. DDM in such network environments has been commonly used to support more intensive interactive simulations. Because of the fundamental differences at both the application layer and the underlying network layer, the study of DDM has to follow very different methodologies, which in turn divert our interests and objectives in each area significantly.
Chapter 6 introduces some background concepts on ubiquitous computing (UC) and then presents the state-of-the-art in the field of middleware for UC. It then addresses the requirement of the integration of UC middleware and describes an existent solution that addresses this requirement, the Open COntext Platform Integration (OpenCOPI). OpenCOPI provides: (i) an automatic service composition; (ii) a standardized context and communication model; and (iii) a fault tolerance mechanism that handles service failures. Another important feature of OpenCOPI is the use of semantic workflows. The composition model adopted by OpenCOPI is based on both services functionalities and services metadata, enabling a better choice between available services with similar functionalities.
Wireless networks are the communication backbone of mobile networks surrounding us. Mobility is an important characteristic of most of personal electronic/computing devices and plays a crucial role both in a positive way (e.g., in delay-tolerant networks) and in a negative way (e.g., creating problems for topology control). Wireless networking is also a key component of today's sensor systems with a wide range of applications. Part 3 is dedicated to some important issues in mobile and wireless networks. It includes five chapters.
Chapter 7 focuses on the challenges faced in the design of new techniques for enabling new decentralized solutions to large scale wireless sensor networks (WSNs) in the Structural Health Monitoring (SHM) domain. First, the definition of SHM along with the concept of WSNs is given. Authors cite several challenges and solutions found in the literature which are considered to be of utmost importance for understanding the context of this domain of WSN applications, guiding further studies in it. This chapter can be a useful reference for everyone who wishes to research in this domain of WSN applications.
Chapter 8 deals with the mobility issue of wireless networks. Mobility is an important factor that affects performance of wireless networks including wireless sensor networks, mobile ad hoc networks, and wireless mesh networks. In fact, the topology of a mobile wireless network is prone to continuous changes, which considerably affect the performance of routing protocols. In order to ease the analysis of mobility effects on the performance of wireless networks, the concept of intermediate performance modeling (IPM) is introduced in this chapter. IPM can divide the analysis into two steps: analysis of the effects of mobility on some intermediate performance measures (e.g., link lifetime), and analysis of the effects of the intermediate performance measures on some final performance measures (e.g., packet loss ratio). Thus, using IPM, one may reuse results of the first step for several evaluations. Moreover, given the results of the first step for several mobility conditions, a particular protocol can be evaluated for all of them.
Chapter 9 considers time-critical WSNs. The WSN should be capable of fulfilling its mission, in a timely manner and without loss of important information. In this chapter, a new analytical model for calculating Real-Time (RT) degree and Reliable Real-Time (RRT) degree in multi-hop WSNs is introduced. Packet loss probability is modeled as a function of the probability of link failure when the buffer is full, and the probability of node failure when the node's energy is depleted. Most network properties are considered as random variables and a queuing theory-based model is derived. In this model, the effect of network load on the packets' delay, RT degree, RRT degree, and node's energy depletion rate are considered.
Chapter 10 gives an overview of the multicast transport protocols. Collaborative Virtual Environments (CVEs) require that geographically distributed users collaborate in closely coupled and highly synchronized tasks to manipulate shared objects. In order to keep the users updated with the changes, and to maintain the synchronization between them, an efficient transport protocol to deliver data is needed. The traditional unicast model that Transport Control Protocol (TCP) offers is inefficient for such applications. In fact, it is not useful to transmit the same data to each receiver across the network. CVE applications use large scale distributed simulations where hundreds or even thousands of distributed users intercommunicate in real time. For this reason, it is necessary to use the multicast approach to deliver data.
As the size of WSNs grows, their complexity increases substantially, rendering traditional centralized control methods unsuitable. Considering the characteristics of WSNs, distributed methods are adopted to solve problems during the process of their design. Most complex problems currently tackled in WSNs share properties with similar scenarios and functions found in nature such as adaptation, self-organization, optimization, topology control, aggregation and communication. These functions are simultaneously handled by biological organisms at different scales and levels to make living creatures more efficient in dealing with different situations. Efficient techniques developed in nature have attracted the attention of computer scientists and engineers for many years and the techniques have been explored and applied to a wide range of problems. Chapter 11 presents a thorough literature survey, introduces the most popular nature-inspired algorithms and shows how these algorithms are applied to a wide range of problems in WSNs.
The grid and cloud computing paradigm has been an incredible success in the last decade. It is based on the idea of delegating every kind of resource to the provider, and letting the users access them in a self-service fashion. The Cloud paradigm has largely been adopted in several different contexts and applied to an incredibly large set of technologies. It is an opportunity for IT users to reduce costs and increase efficiency, providing an alternative way of using IT services. It represents both a technology for using computing infrastructures in a more efficient way and a business model for selling computing resources. It gives small and medium enterprises the possibility of using services and technologies that were the prerogative of large ones, by paying only for the resources needed and avoiding upfront investment. Part 4 is dedicated to different issues of the grid and cloud computing areas and includes eleven chapters.
Chapter 12 discusses Remote Procedure Call (RPC) based computing on grids and clouds. The RPC paradigm is widely used in distributed computing. It provides a straightforward procedure for executing parts of an application on a remote computer. GridRPC is a standard promoted by the Open Grid Forum, which extends the traditional RPC. GridRPC differs from the traditional RPC in that the programmer does not need to specify the server to execute the task. When the programmer does not specify the server, the middleware system is responsible for finding the remote executing server. When the program runs, each GridRPC call results in the middleware mapping the call to a remote server and then the middleware is responsible for the execution of that task on the mapped server. A number of Grid middleware systems have recently become GridRPC compliant including GridSolve, Ninf-G and DIET.
Chapter 13 studies resource allocation in clouds. Pervasive use of cloud computing and the resulting rise in the number of hosting datacenters (which provide platform or software services to clients who do not have the means to set up and operate their own facilities) have brought forth many challenges including energy cost, peak power dissipation, cooling, carbon emission, etc. With power consumption becoming an increasingly important issue for the operation and maintenance of the hosting datacenters, corporate and business owners are becoming increasingly concerned. Furthermore, provisioning resources in a cost-optimal manner so as to meet different criteria such as response time, throughput, network bandwidth, etc. has become a critical challenge. The goal of this chapter is to provide a review of resource provisioning and power management strategies that optimize server-related energy costs in a datacenter while meeting the stipulated service level agreements in terms of throughput and response time.
A strong thrust on the use of virtualization technology to realize Infrastructure-as-a-Service (IaaS) has led enterprises to leverage subscription-oriented computing capabilities of public clouds for hosting their application services. In parallel, research in academia has been investigating transversal aspects such as security, software frameworks, quality of service, and standardization. In Chapter 14, the current status of cloud computing is assessed by providing a reference model, discussing the challenges that researchers and IT practitioners are facing and will encounter in the near future, and presenting the approach for solving them from the perspective of the Cloudbus toolkit, which comprises a set of technologies geared towards the realization of Market Oriented Cloud Computing vision.
Chapter 15 presents a cloud broker architecture for deploying virtual infrastructures across multiple clouds. The main challenges of the brokering problem in multi-cloud environments are analyzed, and different scheduling policies that can guide the brokering decisions, based on cost criteria, performance criteria, resource consumption, etc., are proposed. Some preliminary results are reported in this chapter to prove the benefits of using the proposed broker architecture in a single cloud, using different pricing schemes, and in multi-cloud environments.
Chapter 16 studies energy-efficient resource utilization methods in clouds. In cloud computing systems, the energy consumed by the underutilized resources accounts for a substantial amount of the actual energy consumption. Recent studies reported that energy consumption (in servers) scales linearly with (processor) resource utilization. In this chapter, two existing energy-conscious heuristics for task consolidation are analyzed. Both heuristics aim to maximize resource utilization, with the main difference being whether the energy consumption to execute the given task is implicitly or explicitly considered. To improve the energy efficiency of task consolidation, an algorithm that combines the two heuristics is proposed, in order to take advantage of both. According to the experimental results, the proposed algorithm increases the energy efficiency of the task consolidation problem without performance degradation.
Grid is expected to evolve from a computing and data management facility to a pervasive, world-wide resource-sharing infrastructure. To fully utilize the wide range of grid resources, effective resource discovery mechanisms are required. However, resource discovery in a large-scale grid is challenging due to the considerable diversity, large number, dynamic behavior, and geographical distribution of the resources. Existing resource discovery approaches have difficulties in achieving both rich searchability and good scalability. Chapter 17 investigates the resource discovery problem for open-networked large-scale grids.
Chapter 18 summarizes authors' recent research on game theoretical models of grid user behavior in security-aware scheduling. The main scheduling attributes, generic model of security-aware management in local grid clusters, and several scenarios of users' games are presented. Four GA (Genetic Algorithm)-based hybrid schedulers have been implemented for the approximation of the equilibrium states of the exemplary simple symmetric game of the grid end users. The proposed hybrid resolution methods are empirically evaluated through the grid simulator under the heterogeneity, security, large-scale and dynamic conditions.
The possibility of dynamically acquiring and using resources and services on the basis of a pay-per-use model in clouds, implies incredible flexibility in terms of management, which is otherwise often hard to address. On the other hand, because of this flexibility new problems emerge, which involve the evaluation and monitoring of the quality of the acquired resources and services as well as threats that can compromise performance and availability of services provided to final users. Chapter 19 describes some open challenges to performance evaluation and provisioning in cloud, and presents a survey on the solutions and technologies proposed by researchers and open community to face such issues.
Many data-intensive applications from several fields, including data mining and computational biology, have been modeled as Bag-of-Tasks (BoT) applications. BoT applications are parallel applications whose tasks are independent of each other. In a BoT application, the tasks do not communicate with each other during the execution. Based on the results obtained from the execution of some of the tasks, other tasks may be canceled or modified. Hence cloud computing is an attractive platform for running such BoT applications.
With a plethora of Cloud Service Providers (CSPs) offering various kinds of services, it is quite difficult for a new user to choose an appropriate CSP or a set of CSPs for doing a particular job. Chapter 20 introduces a broker-mediated Cloud Aggregation mechanism for BoT applications wherein the users can submit their applications along with the task execution requirements to the broker, and the broker distributes the tasks to various CSPs based on these requirements.
In Chapter 21, a budget aware scheduler for handling large-scale workflow applications in clouds is proposed. A cloud environment is suitable for a large scale many-task workflow (MTW) to be executed in a scalable manner (e.g., scale up, scale out, and scale down). This chapter proposes a budget-conscious scheduling algorithm for scheduling MTWs on Clouds, referred to as ScaleStar. ScaleStar is able to adapt a selected task to a virtual machine which has a higher comparative advantage so as to effectively balance the execution time and monetary cost. We evaluate the performance of our strategies on six different MTWs from real world applications using three major important metrics.
Chapter 22 focuses on aspects related to performance in private Clouds. Several works have been identified concerning the performance analysis, with focus only on the performance of the virtual environment, not addressing the aspects concerning the operating system, the processor architecture and their impact on performance. In this chapter, an approach is proposed differing from others in the literature, using the virtualization advancements developed so far and the knowledge obtained by tests results to verify the use of hybrid virtual environments. These hybrid models are created based on the characteristics of the running applications, combining the use of different types of hypervisors, and at the same time, using the best features of each, in order to improve the execution performance. The study and evaluation of the use of these hybrid models and their analysis were motivated by a real demand, to provide access to a cloud appliance with a GUI for distributed image processing applications. The basic idea is to offer users remote access to virtualized platforms dedicated to their needs and hosted in a cloud environment.
Part 5 is dedicated to some other important and daily topics in network-based computing. It consists of four chapters.
Chapter 23 considers bandwidth scheduling in e-science networks. Many large-scale scientific and commercial applications produce large amounts of data, of the order of terabytes to petabytes, which must be transferred across wide-area networks. When data providers and consumers are geographically distributed, dedicated bandwidth channels are critical to offer (i) large capacity for massive data transfer operations, and (ii) dynamically stable bandwidth for monitoring and steering operations. Bandwidth reservation systems operate in one of two modes: (a) in on-demand scheduling, bandwidth is reserved for a time period that begins at the current time; (b) in in-advance scheduling, bandwidth is reserved for a time period that begins at some future time. In this chapter, a set of in-advance scheduling problems are defined and corresponding algorithms are proposed and evaluated. Moreover, a multiple path scheduling problem, Earliest Finish Time File Transfer Problem (EFTFTP), is proposed and solved by both optimal solutions and heuristics.
Chapter 24 studies routing and wavelength assignment problems in optical networks. Many high speed networks that provide dedicated connections are based on optical interconnects and optical switches. For these networks, the bandwidth along a given link can be decomposed into multiple wavelengths. The bandwidth scheduling and path computation problem in the context of optical networks is usually called Routing and Wavelength Assignment (RWA). In this chapter, the Extended Bellman-Ford (EBF) algorithm is extended to incorporate the wavelength sharing and wavelength continuity constraints. Moreover, a deferred wavelength assignment strategy is presented. This strategy only counts the number of wavelengths that are used on a link. The actual assignment of the wavelength is done when the request is actually fulfilled. A new network model is proposed which can emulate the existing full-conversion algorithms when only a subset of nodes has a wavelength converter. The algorithms are evaluated on three performance metrics: blocking probability, average start time and scheduling overhead.
Handling the constant stream of data from health care, security, business, and social network applications requires new algorithms and data structures. A new approach for parallel massive analysis of streaming, temporal, graph-structured data is proposed in Chapter 25. This chapter proposes an extensible and flexible data structure for massive graphs called Spatio-Temporal Interaction Networks and Graphs Extensible Representation (STINGER). For the large scale-free graphs, the proposed method uses novel batching techniques that exploit the scale-free nature of the data and run over three times faster than prior methods. This is a new framework which is the first to handle real-world data rates, opening the door to higher-level analytics such as community and anomaly detection.
Chapter 26 presents an ontology-based framework to reflect various aspects of the semantic relationships among the components in the intelligent Water Distribution Network (WDN), and illustrate the powerful automatic reasoning capabilities of the ontology. A complete test case scenario is provided to demonstrate the efficacy of the ontology-based service to assist automatic decision-making in cyber infrastructure when failure occurs in physical infrastructure. By utilizing the ontology to capture the information flow in a complex system, one can have more profound and multi-perspective understanding towards the semantic relationships existing among the interacting components. This is the first time that an ontology-based approach is adopted to assist automatic decision-making based on the raw data collected by sensors, particularly in the domain of WDN. Due to the automatic-reasoning capability of ontology, the ontology-based framework can also be expanded for transportation system and power grid.
Acknowledgments
We should first thank the chapter authors and acknowledge their contributions to the book, as well as their support and patience. We would also like to thank the reviewers for their useful comments and suggestions that helped in improving the earlier outline of the book and presentation of the material. We should extend our deepest thanks to Simone Taylor, Melissa Yanuzzi, and Diana Gialo from Wiley (USA) for their collaboration, guidance, and most importantly, patience in finalizing this volume. Last but not the least, we are very grateful to the lovely team from Wiley's production department for their extensive efforts during the many phases of this project and the timely fashion in which the book was produced.
Hamid Sarbazi-Azad
Sharif University of Technology & IPM
Albert Y. Zomaya
The University of Sydney
List of Contributors
David A. Bader, School of Computational Science and Engineering, Atlanta, GA, USA
Matheus Bousquet Bandini, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Thais Batista, Departamento de Informática e Matemática Aplicada, Centro de Ciências Exatas e da Natureza, Universidade Federal do Rio Grande do Norte, Lagoa Nova, Brazil
Azzedine Boukerche, SITE, University of Ottawa, Ottawa, Ontario, Canada
Pascal Bouvry, Faculty of Science, Technology and Communications, University of Luxembourg, Luxembourg
Thomas Brady, UCD, Dublin, Ireland
Rajkumar Buyya, Cloud Computing and Distributed Systems (CLOUDS) Lab, Department of Computing and Information Systems, The University of Melbourne, Melbourne, Australia
Pasquale Cantiello, Dipartimento di Ingegneria Industriale e dell'Informazione, Second University of Naples, Naples, Italy
Dan Chen, School of Computer Science, China University of Geosciences, Wuhan, China
Claudio M. de Farias, Núcleo de Computação Eletrônica, Universidade Federal do Rio de Janeiro, Brazil
Flávia C. Delicato, Departamento de Ciência da Computação, Instituto de Matemática, Universidade Federal de Rio de Janeiro, Brazil
Henrique de Medeiros Klôh, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Victor Dias de Oliveira, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Bilel Derbel, INRIA Lille-Nord Europe, France
Beniamino Di Martino, Department of Ingegneria Industriale e dell'Informazione, Second University of Naples (SUN), Naples, Italy
Mathieu Djamaï, INRIA Lille-Nord Europe, France
Igor L. dos Santos, Núcleo de Computação Eletrônica, Universidade Federal de Rio de Janeiro, Brazil
David Ediger, School of Computational Science and Engineering, Atlanta, GA, USA
Massimo Ficco, Department of Ingegneria Industriale e dell'Informazione, Second University of Naples (SUN), Naples, Italy
Oleg Girko, UCD, Dublin, Ireland
Nasir Ghani, ECE Department, University of New Mexico, Albuquerque, NM, USA
Hadi Goudarzi, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA, USA
Yunfeng Gu, SITE, University of Ottawa, Ottawa, Ontario, Canada
Ali Hurson, Missouri University of Science and Technology, Rolla, MO, USA
Amir Hossein Jahangir, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Eunsung Jung, Samsung, Seohyun-dong, Kyunggi-do, South Korea
Samee U. Khan, Electrical and Computer Engineering Department, North Dakota State University, Fargo, ND, USA
Joanna Kolodziej, Institute of Computer Science, Cracow University of Technology, Cracow, Poland
Bjorn Landfeldt, Department of Electrical and Information Technology, Lund University, Lund, Sweden
Alexey Lastovetsky, UCD, Dublin, Ireland
Juan Li, Electrical and Computer Engineering Department, North Dakota State University, Fargo, ND, USA
Wei Li, School of Information Technologies, The University of Sydney, Sydney, Australia
Xiaorong Li, Institute of High Performance Computing, A*STAR, Singapore
Yan Li, Google, Cupertino, CA, USA
Jing Lin, Missouri University of Science and Technology, Rolla, MO, USA
Ignacio M. Llorente, Facultad de Informatica, Universidad Complutense de Madrid, Madrid, Spain
Frederico Lopes, Escola de Ciências e Tecnologia, Universidade Federal do Rio Grande do Norte, Lagoa Nova, Brazil
José Luis Lucas-Simarro, Facultad de Informatica, Universidad Complutense de Madrid, Madrid, Spain
Haifa Raja Maamar, SITE, University of Ottawa, Ottawa, Ontario, Canada
Fábio André Machado Porto, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Giacomo Victor McEvoy Valenzano, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Daniel Massami Muniz Yokoyama, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Nouredine Melab, LIFL, Université de Lille 1, France
Henning Meyerhenke, Institute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
Mohand Mezmaz, MathRO, University of Mons, Belgium
Kambiz Mizanian, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Mehdi Modarressi, Electrical and Computer Engineering, College of Engineering, University of Tehran, Tehran, Iran
Ruben S. Montero, Facultad de Informatica, Universidad Complutense de Madrid, Madrid, Spain
Rafael Moreno-Vozmediano, Facultad de Informatica, Universidad Complutense de Madrid, Madrid, Spain
Francesco Moscato, Dipartimento di Ingegneria Industriale e dell'Informazione, Second University of Naples, Naples, Italy
Antonio Roberto Mury, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Abbas Nayebi, Google, Mountain View, CA, USA
Ganesh Neelakanta Iyer, Department of Electrical and Computer Engineering, National University of Singapore (NUS), Singapore
Suraj Pandey, Cloud Computing and Distributed Systems (CLOUDS) Lab, Department of Computing and Information Systems, The University of Melbourne, Melbourne, Australia
Massoud Pedram, Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA, USA
Paulo F. Pires, Departamento de Ciência da Computação, Instituto de Matemática, Universidade Federal de Rio de Janeiro, Brazil
Luci Pirmez, Núcleo de Computação Eletrônica, Universidade Federal do Rio de Janeiro, Brazil
Massimiliano Rak, Department of Ingegneria Industriale e dell'Informazione, Second University of Naples (SUN), Naples, Italy
Sanjay Ranka, CISE Department, University of Florida, Gainesville, FL, USA
Nageswara S. Rao, Oak Ridge National Laboratory, Oak Ridge, TN, USA
Jason Riedy, School of Computational Science and Engineering, Atlanta, GA, USA
Sartaj Sahni, CISE Department, University of Florida, Gainesville, FL, USA
Iñigo San Aniceto, Facultad de Informatica, Universidad Complutense de Madrid, Madrid, Spain
Hamid Sarbazi-Azad, Department of Computer Engineering, Sharif University of Technology and School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
Sahra Sedigh, Missouri University of Science and Technology, Rolla, MO, USA
Franciszek Seredynski, Department of Mathematics and Natural Sciences, Cardinal Stefan Wyszynski University in Warsaw, Warsaw, Poland
Bruno Schulze, Laboratório Nacional de Computação Científica, Petrópolis, Brazil
Javid Taheri, School of Information Technologies, The University of Sydney, Sydney, Australia
Daniel Tuyttens, MathRO, University of Mons, Belgium
Giorgio L. Valentini, Faculty of Science, Technology and Communications, University of Luxembourg, Luxembourg
Christian Vecchiola, Cloud Computing and Distributed Systems (CLOUDS) Lab, Department of Computing and Information Systems, The University of Melbourne, Melbourne, Australia
Bharadwaj Veeravalli, Department of Electrical and Computer Engineering, National University of Singapore (NUS), Singapore
Salvatore Venticinque, Department of Ingegneria Industriale e dell'Informazione, Second University of Naples (SUN), Naples, Italy
Lizhe Wang, Center for Earth Observation and Digital Earth, Chinese Academy of Sciences, Beijing, China
Lingfang Zeng, Department of Electrical and Computer Engineering, National University of Singapore (NUS), Singapore
Albert Y. Zomaya, School of Information Technologies, The University of Sydney, Sydney, Australia
Part 1
Multicore and Many-Core (MC) Systems-On-Chip
1
A Reconfigurable On-Chip Interconnection Network for Large Multicore Systems
Mehdi Modarressi and Hamid Sarbazi-Azad
Contents
1.1 Introduction
1.1.1 Multicore and Many-Core Era
With the recent scaling of semiconductor technology, coupled with the ever-increasing demand for high-performance computing in embedded, desktop, and server computer systems, the current general-purpose microprocessors have been moving from single-core to multicore and eventually to many-core processor architectures containing tens to hundreds of identical cores [1]. Major manufacturers already ship 10-core [2], 16-core [3, 4], and 48-core [5] chip multiprocessors, while some special-purpose processors have pushed the limit further to 188 [6], 200 [7], and 336 [8] cores.
Following the same trend, current multicore system-on-chips (SoC) have grown in size and complexity and consist of tens to hundreds of logic blocks of different types communicating with each other at very-high-speed rates.
