Search

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks ${\mathsf {N}}$ distributed workers to compute a linearly separable function of ${\mathsf {K}}$ datasets, which is a set of ${\mathsf {K}}_{\mathrm{ c}}$ linear combinations of ${\mathsf {K}}$ equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any ${\mathsf {N}}_{\mathrm{ r}}$ out of ${\mathsf {N}}$ workers the master can recover the task function with high probability. In the literature, the specific case where ${\mathsf {K}}_{\mathrm{ c}}=1$ or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general ${\mathsf {K}}_{\mathrm{ c}} $ and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when ${\mathsf {K}}_{\mathrm{ c}}$ is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or ${\mathsf {K}}_{\mathrm{ c}}$ is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases. [ABSTRACT FROM AUTHOR]

Conventional direction-of-arrival (DOA) estimation algorithms are sensitive to array imperfections and outliers, making it challenging to realize accurate estimates in real applications. Facing the challenge, we propose a robust variational Bayesian inference based DOA estimation algorithm using the linear sparse array in this paper, where accurate DOA estimation with increased number of degrees of freedom (DOFs) is realized. With the mixture of von Mises model, a prior-grid scheme is further proposed to alleviate the computational burden introduced by the Bayesian variational inference framework. Since there is no restriction on the prior knowledge of the number of sources, the proposed algorithm is friendly to actual scenarios. Simulation results demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Coded computation techniques provide robustness against straggling workers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behavior and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed scheme in terms of the trade-off between the computation accuracy and latency. [ABSTRACT FROM AUTHOR]

Distributed computing enables parallel execution of smaller tasks that make up a large computing job. Its purpose is to reduce the job completion time. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy provides diversity that allows job completion when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. Under constrained resources (here, a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy among replication, coding, and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe the scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different redundancy levels, thus requiring very different code rates. [ABSTRACT FROM AUTHOR]

Temporal decomposition is a potential approach to relieve the computation cost of power system multi-interval scheduling problems, such as economic dispatch. In this form of decomposition, the considered scheduling horizon is partitioned into several subhorizons. A subproblem is formulated for each subhorizon, and a distributed optimization algorithm strategy is used to coordinate subproblems. The main existing challenge is decomposing the scheduling horizon to gain the most time saving from distributed computing. This paper serves as an extension to our previous work and presents a machine learning-aided temporal decomposition strategy to partition a scheduling horizon optimally. We have found that the load profile, known before solving economic dispatch, significantly affects the best number of subhorizons. We have used load profiles as inputs to a learner whose goal is to assign a temporal decomposition class to each load profile. Possible decomposition classes are divisors of the considered scheduling horizon. Thus, the proposed learning procedure is a multiclass classification. We have selected Extreme Gradient Boosting that is a tree-based classification learner. Simulation results using real-world load profiles show the promising performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The paper surveys the state of the art of task scheduling in Desktop Grid computing systems. We describe the general architecture of a Desktop Grid system and the computing model adopted by the BOINC middleware. We summarize research papers to bring together and examine the optimization criteria and methods proposed by researchers so far for improving Desktop Grid task scheduling (assigning tasks to computing nodes by a server). In addition, we review related papers, which address non-regular architectures, like hierarchical and peer-to-peer Desktop Grids, as well as Desktop Grids designed for solving interdependent tasks. [ABSTRACT FROM AUTHOR]

Compared to binary-state system models, multistate (MS) system models are more practical and useful when describing complex systems in applications, such as communication systems, oil pipeline systems, and grid or cloud computing infrastructures. This paper models a generalized sparsely connected MS consecutive- ${k}$ -out-of- ${n}$ : ${G}$ system. The proposed model is regarded as a natural extension of the consecutive- ${k}$ -out-of- ${n}$ system. Moreover, the proposed system model could cover three special MS submodels, i.e., a decreasing MS: ${G}$ system model, an increasing MS: ${G}$ system model, and a nonmonotonic MS: ${G}$ system model. Three corresponding real-world examples are given to illustrate the applications of the model. Meanwhile, by utilizing the well-known finite Markov chain imbedding method, the explicit system reliability and state distribution for the three kinds of submodels are presented, respectively. Finally, the developed indexes and analysis method are demonstrated by numerical examples. [ABSTRACT FROM AUTHOR]

On-grid brown energy consumption of cellular infrastructure is contributing to the detrimental impact on the environment, among which base stations (BSs) are guzzling the largest amount of energy in powering the cellular infrastructure. Leveraging green (renewable) energy to power cellular BSs is a radical energy solution. However, in order to minimize the consumption of on-grid brown energy, most related researches focus on maximizing the utilization of green energy in cellular BSs while compromising the user quality of service (QoS). In this paper, we jointly consider the network QoS and green energy utilization in the dual-battery architecture enabled green cellular network. The profit-driven user association and smart grid green energy transfer scheme is proposed to benefit the network providers, in which, some heuristics are further developed to reduce the computational complexity, as the profit-driven user association problem is NP-hard. Extensive simulations have been conducted to validate the proposed scheme. The systematic analysis of this work can serve as a benchmark for greening other information and communication technology infrastructures. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of placing a simple polygon (upon translation and rotation) on an isometric triangular grid such that the polygon contains the maximum number of triangles in its closure. This solves the problem left open in two recent papers titled “On the problem of the automated design of large-scale robot skin” and “An improved algorithm for the automated design of large scale robot skin” published in the IEEE Transactions on Automation Science and Engineering . Based on the properties of the grid, an improved algorithm is also presented. We also present some experimental results describing the use of this algorithm. [ABSTRACT FROM AUTHOR]

Hundreds of papers on job scheduling for distributed systems are published every year and it becomes increasingly difficult to classify them. Our analysis revealed that half of these papers are barely cited. This paper presents a general taxonomy for scheduling problems and solutions in distributed systems. This taxonomy was used to classify and make publicly available the classification of $109$ scheduling problems and their solutions. These $109$ problems were further clustered into ten groups based on the features of the taxonomy. The proposed taxonomy will facilitate researchers to build on prior art, increase new research visibility, and minimize redundant effort. [ABSTRACT FROM PUBLISHER]

Real-time power line outage detection (POD) and localization is an important monitoring task for the modern smart grid. Reliable monitoring of power lines status plays a critical role in the system-wide blackout prevention. In this paper, the main aim is to address the multiple POD problems by exploiting the compressive system identification—a time-efficient approach in a complex network analysis. A typical power network is considered as a single graph, and the mathematical formulation of the POD problem is initialized using the dc power-flow model and graph theory concepts. Next, a sparse representation-based formulation for this problem (POD-SRP) is reported and further improved and generalized in case of multiple large-scale outages. Practical and technical challenges associated with this sparse recovery problem are partially addressed by developing new SRP solvers. Furthermore, a new sparse-based mathematical formulation for POD is introduced and termed as “Binary-POD-SRP,” which specifically deals with two particular issues, namely, the high coherence and the signal dynamic outrange. Finally, the identification performance of the proposed framework is evaluated by a variety of case studies, which are modeled using IEEE standard test-beds. We specifically discuss how the inherent challenges within large-scale multiple-outages can be solved by applying these new techniques and formulations. [ABSTRACT FROM AUTHOR]

The increasing penetration of renewable energy resources, such as wind and solar, is changing AC grid dynamics. Potential dynamic stability issues such as small signal instability may occur when these resources are connected to a grid with low strength, i.e., a weak grid. In this paper, the relationships between small signal stability and grid strength measured with short circuit ratio (SCR), along with the relationships between the stability boundary and critical SCR (CSCR) are analytically studied in a single-infeed power electronic system (SIPES). On this basis, these relationships are extended to a multi-infeed power electronic system (MIPES) through eigenvalue decomposition techniques to define the so-called generalized short circuit ratio (gSCR) and critical gSCR (CgSCR) for small signal stability analysis. The defined gSCR and CgSCR are the generalized representation of SCR and CSCR for SIPESs in MIPESs. The gSCR can assess the grid strength of a MIPES in terms of its small signal stability while the CgSCR can characterize the stability boundary of a MIPES. In addition, the condition of CgSCR = CSCR is satisfied for a MIPES with homogeneous power electronic devices. This enables the proposed method based on the gSCR to simplify the complex stability analysis of MIPESs into the stability study of SIPESs. The efficacy of the proposed gSCR and CgSCR is validated with eigenvalue analysis and time-domain simulations. [ABSTRACT FROM AUTHOR]

Current communication networks are facing more and more threats from large-scale regional damages, such as natural disasters (e.g., earthquake or tornado) and physical attacks (e.g., electromagnetic pulse attack or dragging anchors). Recently, several region failure models have been proposed to evaluate the impact of such geographically correlated failures on communication networks. These works mainly adopt a kind of “deterministic” models, where network components within the affected area would fail simultaneously. Such failure models simplify the analysis but may fail to reflect some important behaviors of attacks and thus cause significant over- or under-estimation of region failures. To emulate the impact of realistic catastrophe events such as earthquake and tornado, this paper introduces two probabilistic failure models: 1) a concentric circle model and 2) a line segment model. In the probabilistic models, both the location and effect of the damage are treated as random events. The failure may randomly incur on the entire network plane, and the failure probability of a device depends on many factors, e.g., link length and distance to the damage center. We develop an efficient grid partition-based scheme to estimate the network vulnerability. Based on the grid partition scheme, we further develop a sampling scheme to significantly reduce the computation cost. The probability model helps us more deeply understand the network behaviors under region failure and facilitates the design and maintenance of future highly survivable mission critical networks. [ABSTRACT FROM AUTHOR]

This paper introduces quantum computing as a necessary and viable tool in addressing the needs of a modernized power grid. The application of quantum computing in enhancing physical security of the grid – an increasingly difficult problem to solve– is investigated. A comparative study based on mathematically proven computing performance measures shows the merits of the proposed method and further unveils the potential benefits of quantum computing in improving grid performance. [ABSTRACT FROM AUTHOR]

High performance grid computing is a key enabler of large scale collaborative computational science. With the promise of exascale computing, high performance grid systems are expected to incur electricity bills that grow super-linearly over time. In order to achieve cost effectiveness in these systems, it is essential for the scheduling algorithms to exploit electricity price variations, both in space and time, that are prevalent in the dynamic electricity price markets. In this paper, we present a metascheduling algorithm to optimize the placement of jobs in a compute grid which consumes electricity from the day-ahead wholesale market. We formulate the scheduling problem as a Minimum Cost Maximum Flow problem and leverage queue waiting time and electricity price predictions to accurately estimate the cost of job execution at a system. Using trace based simulation with real and synthetic workload traces, and real electricity price data sets, we demonstrate our approach on two currently operational grids, XSEDE and NorduGrid. Our experimental setup collectively constitute more than 433K processors spread across 58 compute systems in 17 geographically distributed locations. Experiments show that our approach simultaneously optimizes the total electricity cost and the average response time of the grid, without being unfair to users of the local batch systems. [ABSTRACT FROM AUTHOR]

Three-phase cascaded inverter with leakage current reduction for the transformerless PV system is investigated in this paper. The common-mode loop model of the conventional three-phase cascaded H4 grid-connected inverter is established. The relationship among the leakage current, common-mode voltage, and differential mode voltage is analyzed. The inherent reason that the conventional cascaded H4 grid-connected inverter fails to reduce the leakage current is clarified. In order to solve the problem, a novel three-phase cascaded H5 grid-connected inverter and its modulation strategy are proposed. It can significantly reduce the leakage current. Finally, the performance tests of the cascaded H4 and H5 grid-connected inverters are carried out. The results verify the effectiveness of the proposed solution. [ABSTRACT FROM PUBLISHER]

Inverter-based distributed generation (DG) system is becoming an attractive solution for high penetration of renewable energy sources to the main grid. DG system should be able to supply power to the local loads whenever necessary even in case of utility power outage. Thus, the inverters in DG systems are expected to operate in both grid-connected and islanded mode, where they are acting as a current source for the ac grid and a voltage-source for the load, respectively. Transition between modes of operation is nontrivial and can cause deviations in voltage and current, because of mismatch in frequency, phase, and amplitude between the inverter output voltage and the grid voltage. Thus, it is necessary to have seamless transition between grid-connected and islanded mode. This paper presents a new control strategy with seamless transfer characteristics for a grid-connected voltage-source inverter using model predictive control (MPC) framework. The main objectives of the proposed predictive controller are: 1) decoupled power control in grid-connected mode, which enables the proposed power electronics interface to provide ancillary services such as reactive power compensation; 2) load voltage control in islanded mode; and 3) seamless transition between modes of operation through proposed synchronization and phase adjustment algorithm. The proposed controller features simplicity to implement since only one cost function should be minimized for all modes of operation, and hence no ambiguity in the control algorithm that could cause mode transition problems. An autotuning strategy for weight factors in MPC cost function is proposed to simplify the weight factor tuning strategy. The stability analysis of the proposed controller is provided. Simulation and experimental results validate the expected performance and effectiveness of the proposed control strategy. [ABSTRACT FROM PUBLISHER]

Solving to optimality large instances of combinatorial optimization problems using Brand and Bound (B&B) algorithms requires a huge amount of computing resources. In this paper, we investigate the design and implementation of such algorithms on computational grids. Most of existing grid-based B&B algorithms are based on the Master-Worker paradigm, their scalability is therefore limited. In addition, even if the volatility of resources is a major issue in grids fault tolerance is rarely addressed in these works. We thereby propose FTH-B&B, a fault tolerant hierarchical B&B. FTH-B&B is based on different new mechanisms enabling to efficiently build and maintain balanced the hierarchy, and to store and recover work units (sub-problems). FTH-B&B has been implemented on top of the ProActive grid middleware and programming environment and applied to the Flow-Shop scheduling problem. Very often, the validation of existing grid-based B&B works is performed either through simulation or a very small real grid. In this paper, we experimented FTH-B&B on the Grid’5000 real French nation-wide computational grid using up to 1,900 processor cores distributed over six sites. The reported results show that the overhead induced by the proposed mechanisms is very low and an efficiency close to 100 percent can be achieved on some Taillards benchmarks of the Flow-Shop problem. In addition, the results demonstrate the robustness of the proposed mechanisms even in extreme failure situations. [ABSTRACT FROM PUBLISHER]

In this paper, a prototype of an energy monitoring device based on an open source concept is presented. This architecture assures several advantages with respect to traditional energy meters, such as easy development of new applications making cost- and time-effective the migration to future smart grid infrastructures and simple adjustments to change in the relevant standards. The open source philosophy has been adopted designing the software components to make all features easily customizable by the user. In this paper, the characterization of the acquisition channels using measurement data obtained stimulating them with signals generated using a high-accuracy waveform generation module is presented. [ABSTRACT FROM PUBLISHER]

With the increasing attention to the concept of microgrids, it has become important to identify the requirements that enable an electric distribution network to operate as a microgrid. This paper studies a realistic distribution network to accomplish the following: 1) determine the conditions under which the network can operate as a microgrid and 2) present the control scenarios that allow the islanded operation of the network. In particular, the employment of electronically coupled distributed energy resources with the fault-ride-through and synchronization capabilities is investigated. Another objective of this paper is to propose practical protection strategies that are effective in both operational modes of a microgrid (i.e., the grid-connected mode and the islanded mode), considering the system constraints; the protection strategies provide the microgrid with acceptable reliability against different fault scenarios. The effectiveness of the control and protection strategies is demonstrated and discussed through a comprehensive set of simulation studies conducted in the PSCAD/EMTDC software environment. [ABSTRACT FROM PUBLISHER]

In a recent paper by Yaakobi and Bruck, the problem of information retrieval in associative memories has been considered. In an associative memory, each memory entry is associated to the neighboring entries. When searching information, a fixed number of input clues are given and the output set is formed by the entries associated to all the input clues. The maximum size of an output set is called the uncertainty of the associative memory. In this paper, we study the problem of information retrieval in associative memories with small uncertainty. In particular, we concentrate on the cases where the memory entries and their associations form a binary Hamming space or an infinite square grid. Particularly, we focus on minimizing the number of input clues needed to retrieve information with small uncertainty and present good constructions some of which are optimal, i.e., use the smallest possible number of clues. [ABSTRACT FROM AUTHOR]

Recently, data replication has received considerable attention in the field of grid computing. The main goal of data replication algorithms is to optimize data access performance by replicating the most popular files. When a file does not exist in the node where it was requested, it necessarily has to be transferred from another node, causing delays in the completion the file requests. The general idea behind data replication is to keep track of the most popular files requested in the grid and create copies of them in selected nodes. In this way, more file requests can be completed over a period of time and average job execution time is reduced. In this paper, we introduce an algorithm that estimates the potential of the files located in each node of the grid, using a binary tree structure. Also, the file scope and the file type are taken into account. By potential of a file, we mean its increasing or decreasing demand over a period of time. The file scope generally refers to the extent of the group of users which are interested or potentially interested in a file. The file types are divided into read and write intensive. Our scheme mainly promotes the high-potential files for replication, based on the temporal locality principle. The simulation results indicate that the proposed scheme can offer better data access performance in terms of the hit ratio and the average job execution time, compared to other state-of-the-art strategies. [ABSTRACT FROM PUBLISHER]

Depth map sensed by low-cost active sensor is often limited in resolution, whereas depth information achieved from structure from motion or sparse depth scanning techniques may result in a sparse point cloud. Achieving a high-resolution (HR) depth map from a low resolution (LR) depth map or densely reconstructing a sparse non-uniformly sampled depth map are fundamentally similar problems with different types of upsampling requirements. The first problem involves upsampling in a uniform grid, whereas the second type of problem requires an upsampling in a non-uniform grid. In this paper, we propose a new approach to address such issues in a unified framework, based on sparse representation. Unlike, most of the approaches of depth map restoration, our approach does not require an HR intensity image. Based on example depth maps, sub-dictionaries of exemplars are constructed, and are used to restore HR/dense depth map. In the case of uniform upsampling of LR depth map, an edge preserving constraint is used for preserving the discontinuity present in the depth map, and a pyramidal reconstruction strategy is applied in order to deal with higher upsampling factors. For upsampling of non-uniformly sampled sparse depth map, we compute the missing information in local patches from that from similar exemplars. Furthermore, we also suggest an alternative method of reconstructing dense depth map from very sparse non-uniformly sampled depth data by sequential cascading of uniform and non-uniform upsampling techniques. We provide a variety of qualitative and quantitative results to demonstrate the efficacy of our approach for depth map restoration. [ABSTRACT FROM PUBLISHER]

Clouds are becoming an important platform for scientific workflow applications. However, with many nodes being deployed in clouds, managing reliability of resources becomes a critical issue, especially for the real-time scientific workflow execution where deadlines should be satisfied. Therefore, fault tolerance in clouds is extremely essential. The PB (primary backup) based scheduling is a popular technique for fault tolerance and has effectively been used in the cluster and grid computing. However, applying this technique for real-time workflows in a virtualized cloud is much more complicated and has rarely been studied. In this paper, we address this problem. We first establish a real-time workflow fault-tolerant model that extends the traditional PB model by incorporating the cloud characteristics. Based on this model, we develop approaches for task allocation and message transmission to ensure faults can be tolerated during the workflow execution. Finally, we propose a dynamic fault-tolerant scheduling algorithm, FASTER, for real-time workflows in the virtualized cloud. FASTER has three key features: 1) it employs a backward shifting method to make full use of the idle resources and incorporates task overlapping and VM migration for high resource utilization, 2) it applies the vertical/horizontal scaling-up technique to quickly provision resources for a burst of workflows, and 3) it uses the vertical scaling-down scheme to avoid unnecessary and ineffective resource changes due to fluctuated workflow requests. We evaluate our FASTER algorithm with synthetic workflows and workflows collected from the real scientific and business applications and compare it with six baseline algorithms. The experimental results demonstrate that FASTER can effectively improve the resource utilization and schedulability even in the presence of node failures in virtualized clouds. [ABSTRACT FROM AUTHOR]

This paper adapts overlapped block motion compensation (OBMC) to suit variable block-size motion partitioning. The motion vectors (MVs) for various partitions are formalized as motion samples taken on an irregular grid. From this viewpoint, determining OBMC weights to associate with these samples becomes an under-determined problem since a distinct solution has to be sought for each prediction pixel. In this paper, we tackle this problem by expressing the optimal weights in closed form based on parametric signal assumptions. In particular, the computation of this solution requires only the geometric relations between the prediction pixel and its nearby block centers, leading to a generic framework capable of reconstructing temporal predictors from any irregularly sampled MVs. A modified implementation is also proposed to address the MV location uncertainty and to reduce computational complexity. Experimental results demonstrate that our scheme performs better than similar previous works, and when compared to the recently proposed Quadtree-based adaptive loop filter and enhanced adaptive interpolation filter, show a comparable gain. Furthermore, the combination of it with either of them gives a combined effect that is almost the sum of their separate improvements. [ABSTRACT FROM PUBLISHER]

Distributed virtual machines can help to build scalable, manageable, and efficient grid infrastructures. The work proposed in this paper focuses on employing virtual machines for grid computing. In order to efficiently run grid applications, virtual machine resource information should be provided. This paper first discusses the system architecture of virtual machine pools and the process of information retrieval from virtual machines. Based on the characterization of the system model, this paper presents the work on how to retrieve resource information from Xen/VMware virtual machines via VMware Common Information Model Software Development Kit and lightweight Java agents. The resource information is integrated into a grid information service. The work is implemented in a test bed with Xen/VMware virtual machines and the Globus Toolkit. With a performance evaluation and discussion on a real test bed, it is declared that the design and implementation of information services for virtual-machine-based grid systems are feasible, efficient, and scalable. [ABSTRACT FROM PUBLISHER]

Predicting grid performance is a complex task because heterogeneous resource nodes are involved in a distributed environment. Long execution workload on a grid is even harder to predict due to heavy load fluctuations. In this paper, we use Kalman filter to minimize the prediction errors. Weapply Savitzky-Golay filter to train a sequence of confidence windows. The purpose is to smooth the prediction process from being disturbed by load fluctuations. We present a new adaptive hybrid method (AHModel) for load prediction guided by trained confidence windows. We test the effectiveness of this new prediction scheme with real-life workload traces on the AuverGrid and Grid5000 in France. Both theoretical and experimental results are reported in this paper. As the lookahead span increases from 10 to 50 steps (5 minutes per step), the AHModel predicts the grid workload with a mean-square error (MSE) of 0.04-0.73 percent, compared with 2.54-30.2 percent in using the static point value autoregression (AR) prediction method. The significant gain in prediction accuracy makes the new model very attractive to predict Grid performance. The model was proved especially effective to predict large workload that demands very long execution time, such as exceeding 4 hours on the Grid5000 over 5,000 processors. With minor changes of some system parameters, the AHModel can apply to other computational grids as well. At the end, we discuss extended research issues and tool development for Grid performance prediction. [ABSTRACT FROM AUTHOR]

The design trades made in choosing an appropriate protocol for the conveyance of meter data are discussed. The paper identifies "context" as the mechanism by which communication efficiencies are sometimes obtained. This paper concludes that while generalized protocols are commonly used to communicate between utility back-office applications, specialized protocols can yield an optimum solution when reaching endpoints. [ABSTRACT FROM AUTHOR]

This paper presents a new operational strategy for a small scale wind farm which is composed of both fixed and variable speed wind turbine generator systems (WTGS). Fixed speed wind generators suffer greatly from meeting the requirements of new wind farm grid code, because they are largely dependent on reactive power. Integration of flexible ac transmission systems (FACTS) devices is a solution to overcome that problem, though it definitely increases the overall cost. Therefore, in this paper, we focuses on a new wind farm topology, where series or parallel connected fixed speed WTGSs are installed with variable speed wind turbine (VSWT) driven permanent magnet synchronous generators (PMSG). VSWT-PMSG uses a fully controlled frequency converter for grid interfacing and it has abilities to control its reactive power as well as to provide maximum power to the grid. Suitable control strategy is developed in this paper for the multilevel frequency converter of VSWT-PMSG. A real grid code defined in the power system is considered to analyze the low voltage ride through (LVRT) characteristic of both fixed and variable speed WTGSs. Moreover, dynamic performance of the system is also evaluated using real wind speed data. Simulation results clearly show that the proposed topology can be a cost effective solution to augment the LVRT requirement as well as to minimize voltage fluctuation of both fixed and variable speed WTGSs. [ABSTRACT FROM AUTHOR]

Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo et al. do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-slice line grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day. [ABSTRACT FROM AUTHOR]

This paper focuses on representing the state space model of a microgrid in which power regulated (PQ ) and voltage/frequency regulated (Vf) generation units share a distribution system. The generation units considered in this paper are inverter interfaced. This introduces some interesting modeling problems which are treated in the paper, such as the decoupled cascaded control schemes or the non-negligible grid dynamics. A modeling approach is proposed based on four defined complex vectors. These vectors allow for complex-valued system matrices to be formed in a quite automated way. Moreover, a convenient partition of the system matrices is proposed, which in turn allows fast and easy modifications. Additionally, a multivariable methodology is proposed to simultaneously find the control system gains in an optimal sense. A 69-bus radial system, supplied by 20 generation units, is used to demonstrate how the proposal is of easy implementation to conduct small-signal stability analyses. [ABSTRACT FROM AUTHOR]

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as "information overlapping-data coverage" challenge. Current solutions of subspace clustering usually invoke a grid-based Apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in Apriori- like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the "data coverage" issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "NOnRedundant Subspace Cluster mining" (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works. [ABSTRACT FROM AUTHOR]

Service discovery is a crucial operation for the usability of mobile ad hoc networks (MANETs). Traditional solutions to service discovery that were adopted on the Internet are not well suited for MANETs because of their dynamic nature. This paper presents a novel service discovery protocol based on a hierarchical grid architecture in an ad hoc network. The geographical area of a MANET is divided into a 2-D logical hierarchical grid. The proposed scheme registers the information of available services to a specific location along a predefined trajectory. To enhance resource availability and effective discovery, each grid cell selects a directory for caching available services. This paper utilizes the transmitting trajectory to improve the efficiency of registration and discovery. First, the service provider registers a service along the proposed register trajectory. The requestor then discovers the service along the discovery trajectory to acquire the service information. This paper also proposes an improved process to avoid the sparse node network topology. This paper adopts analysis and simulation to measure the protocol performance. The analytical and simulation results show that the proposed protocol can raise the discovery success ratio and reduce the discovery cost more than the existing geographical service discovery protocol. [ABSTRACT FROM AUTHOR]

Abstract-Data Distribution Management (DDM) is one of the most critical component of any large-scale interactive distributed simulation systems. The aim of DDM is to reduce and control the volume of information exchanged among the simulated entities (federates) in a large-scale distributed simulation system. In order to fulfill its goal, a considerable amount of DDM messages needs to be exchanged within the simulation (federation). The question of whether each message should be sent immediately after it is generated or held until it can be grouped with other DDM messages needs to be investigated further. Our experimental results have shown that the total DDM time of a simulation varies considerably depending on which transmission strategy is used. Moreover, in the case of grouping, the DDM time depends on the size of the group. In this paper, we propose a novel DDM approach, which we refer to as Adaptive Grid-based (AGB) DDM. The AGB protocol is distinct from all existing DDM implementations, because it is able to predict the average amount of data generated in each time step of a simulation. Therefore, the AGB DDM approach controls a simulation running in the most appropriate mode to achieve a desired performance. This new DDM approach consists of two adaptive control parts: 1) the Adaptive Resource Allocation Control (ARAC) scheme and 2) the Adaptive Transmission Control (ATC) scheme. The focus of this paper is on the ATC scheme. We describe how to build a switching model to predict the average amount of DDM messages generated and how the ATC scheme uses this estimation result to optimize the overall DDM time. Our experimental results provide a clear evidence that the ATC scheme is able to achieve the best performance in DDM time when compared to all existing DDM protocols using an extensive set of experimental case studies. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new algorithm for fair scheduling, and we compare it to other scheduling schemes such as the Earliest Deadline First (EDF) and the First Come First Served (FCFS) schemes. Our algorithm uses a max-min fair sharing approach for providing fair access to users. When there is no shortage of resources, the algorithm assigns to each task enough computational power for it to finish within its deadline. When there is congestion, the main idea is to fairly reduce the CPU rates assigned to the tasks so that the share of resources that each user gets is proportional to the user's weight. The weight of a user may be defined as the user's contribution to the infrastructure or the price he is willing to pay for services or any other socioeconomic consideration. In our algorithms, all tasks whose requirements are lower than their fair share CPU rate are served at their demanded CPU rates. However, the CPU rates of tasks whose requirements are larger than their fair share CPU rate are reduced to fit the total available computational capacity in a fair manner. Three different versions of fair scheduling are adopted in this paper: the Simple Fair Task Order (SFTO), which schedules the tasks according to their respective fair completion times, the Adjusted Fair Task Order (AFTO), which refines the SFTO policy by ordering the tasks using the adjusted fair completion time, and the Max-Min Fair Share (MMFS) scheduling policy, which simultaneously addresses the problem of finding a fair task order and assigning a processor to each task based on a max-min fair sharing policy. Experimental results and comparisons with traditional scheduling schemes such as the EDF and the FCFS are presented using three different error criteria. Validation of the simulations using real experiments of tasks generated from 3D image- rendering processes is also provided. The three proposed scheduling schemes can be integrated into existing Grid computing architectures. [ABSTRACT FROM AUTHOR]

Grid computing is a recently developed technology. Although the developmental tools and techniques for the grid have been extensively studied, grid reliability analysis is not easy because of its complexity. This paper is the first one that presents a hierarchical model for the grid service reliability analysis and evaluation. The hierarchical modeling is mapped to the physical and logical architecture of the grid service system and makes the evaluation and calculation tractable by identifying the independence among layers. Various types of failures are interleaved in the grid computing environment, such as blocking failures, time-out failures, matchmaking failures, network failures, program failures, and resource failures. This paper investigates all of them to achieve a complete picture about grid service reliability. Markov models, Queuing theory, and Graph theory are mainly used here to model, evaluate, and analyze the grid service reliability. Numerical examples are illustrated. [ABSTRACT FROM AUTHOR]

A comprehensive suite of pedagogical resources is presented that will enable an instructor to embed grid computing concepts in a traditional distributed system course. Rapidly advancing Internet technologies and ever expanding application domains have created excitement in teaching distributed systems. Many fundamental concepts developed decades earlier, such as remote procedure calls and multithreading, have come to play key roles in modern distributed systems. Standards such as eXtensible Markup Language (XML) and Simple Object Access Protocol (SOAP) have been developed to enable interoperability among heterogeneous distributed systems. However, a plethora of new paradigms, a wide variety of technological choices, and short cycles of technological obsolescence challenge the introduction of these important concepts into a distributed systems course. This paper describes how the author addressed these challenges in teaching grid computing. The paper also provides details of the resources developed during this process. The pedagogical resource kit developed includes course curriculum, lecture notes, a set of laboratory assignments, a Globus Toolkit-based experimental grid adapted to classroom assignments, and valuable lessons learned from the course offerings during the past two years. The material provided in this paper is expected to help to ‘jumpstart’ educators considering the introduction of grid computing into their curricula. [ABSTRACT FROM AUTHOR]

Grid protocols and technologies are being adopted in a wide variety of academic, government, and industrial environments, and a growing body of research-oriented literature in grid computing is being compiled. However, there is a need for educational material that is suitable for classroom use. This paper describes topics, exercises, and experiences of teaching grid computing at two different universities. Course material in grid computing can be grouped into several knowledge areas. The focus in this paper is on grid programming, i.e., developing grid-enabled services using the Globus toolkit. Assessment data shows that with preparatory material and hands-on exercises, undergraduate computer science students can master grid programming. Topics and exercises for security, network programming, Web services, and grid programming are described. Recommendations include using stand-alone containers on individual student computers and following a first grid programming exercise that builds confidence with at least one more elaborate grid programming exercise. [ABSTRACT FROM AUTHOR]

Scheduling stochastic workloads is a difficult task. In order to design efficient scheduling algorithms for such workloads, it is required to have a good in-depth knowledge of basic random scheduling strategies. This paper analyzes the distribution of sequential jobs and the system behavior in heterogeneous computational grid environments where the brokering is done in such a way that each computing element has a probability to be chosen proportional to its number of CPUs and (new from the previous paper) its relative speed. We provide the asymptotic behavior for several metrics (queue sizes, slowdowns, etc.) or, in some cases, an approximation of this behavior. We study these metrics for a variety of workload configurations (load, distribution, etc.). We compare our probabilistic analysis to simulations in order to validate our results. These results provide a good understanding of the system behavior for each metric proposed. This will enable us to design advanced and efficient algorithms for more complex cases. [ABSTRACT FROM AUTHOR]

Data mining algorithms are widely used today for the analysis of large corporate and scientific datasets stored in databases and data archives. Industry, science, and commerce fields often need to analyze very large datasets maintained over geographically distributed sites by using the computational power of distributed and parallel systems. The grid can play a significant role in providing an effective computational support for distributed knowledge discovery applications. For the development of data mining applications on grids we designed a system called KNOWLEDGE GRiD. This paper describes the KN0WIADGE (kim framework and presents the tool set provided by the KNOWLEDGE Gno for implementing distributed knowledge discovery. The paper discusses how to design and implement data mining applications by using the KNOWLEDGE GRW tools starting from searching grid resources, composing software and data components, and executing the resulting data mining process on a grid. Some performance results are also discussed. [ABSTRACT FROM AUTHOR]

Automatically predicting performance of parallel applications has been a long-standing goal in the area of high performance computing. However, accurate performance prediction is challenging, since the execution time of parallel applications is determined by several factors, such as sequential computation time, communication time and their complex interactions. Despite previous efforts, accurately estimating the sequential computation time in each process for large-scale parallel applications remains an open problem. In this paper, we propose a novel approach to acquiring accurate sequential computation time using a parallel debugging technique called deterministic replay. The main advantage of our approach is that we only need a single node of a target platform but the whole target platform does not need to be available. Therefore, with this approach we can simply measure the real sequential computation time on a target node for each process on by one. Moreover, we observe that there is great computation similarity in parallel applications, not only within each process but also among different processes. Based on this observation, we further propose representative replay that can significantly reduce replay overhead, because we only need to replay partial iterations for representative processes instead of all of them. Finally, we implement a complete performance prediction system, called Phantom, which combines the above computation-time acquisition approach and a trace-driven simulator. We validate our approach on both traditional HPC platforms and the latest Amazon EC2 cloud platform. On both types of platforms, prediction error of our approach is less than 7 percent on average up to 2,500 processes. [ABSTRACT FROM AUTHOR]

Pin assignment and escape routing are two closely related problems and it is desired to consider routability during pin assignment for package-board co-design. During pin assignment and escape routing, differential pairs and blind-via usage are two major factors to be considered in modern printed circuit board designs. However, most previous works only target on either differential pairs or blind-via usage but cannot handle both of them simultaneously. In this paper, we propose the first package-board co-design method to optimize the pin assignment and escape routing in the presence of differential pairs and blind-via usage for grid pin array. Experimental results show that our package-board co-design flow can achieve wirelength improvement and reduce the number of layers required compared with competitive baseline flows. [ABSTRACT FROM PUBLISHER]

A large-scale resource sharing system (e.g., collaborative cloud computing and grid computing) creates a virtual supercomputer by providing an infrastructure for sharing tremendous amounts of resources (e.g., computing, storage, and data) distributed over the Internet. A resource information service, which collects resource data and provides resource search functionality for locating desired resources, is a crucial component of the resource sharing system. In addition to resource discovery speed and cost (i.e., efficiency), the ability to accurately locate all satisfying resources (i.e., fidelity) is also an important metric for evaluating service quality. Previously, a number of resource information service systems have been proposed based on Distributed Hash Tables (DHTs) that offer scalable key-based lookup functions. However, these systems either achieve high fidelity at low efficiency, or high efficiency at low fidelity. Moreover, some systems have limited flexibility by only providing exact-matching services or by describing a resource using a pre-defined list of attributes. This paper presents a resource information service that offers high efficiency and fidelity without restricting resource expressiveness, while also providing a similar-matching service. Extensive simulation and PlanetLab experimental results show that the proposed service outperforms other services in terms of efficiency, fidelity, and flexibility; it dramatically reduces overhead and yields significant enhancements in efficiency and fidelity. [ABSTRACT FROM AUTHOR]

We present a novel computational framework that is capable of dealing with many real-world visual tracking problems. A novel spatio-temporal weighting scheme is introduced to maximize the separation between target and background, improving classification accuracy. These weights are then used to define a norm over which a constrained adaptive sparse representation (CASR) of target and background patches is computed. This representation defines a similarity metric that is used by a novel particle-based NormalHedge (NH) algorithm to identify the target on subsequent frames. If the NH algorithm is successful in cleanly identifying the target, the target and background dictionaries are updated according to an adaptive algorithm, which avoids the addition of aberrant or redundant atoms and deletes atoms that have become uninformative. The spatio-temporal weights are then updated and the weighting-CASR-NH-dictionary selection loop starts over again. If the NH algorithm is unsuccessful in cleanly identifying the target, a computationally efficient sparse classifier grid is used for target retrieval. In this paper, we discuss the details of the techniques proposed and compare the accuracy and computational efficiency of the resulting algorithm with that of several existing algorithms. These comparisons demonstrate the value of the proposed algorithm to the solution of real-world online tracking problems. [ABSTRACT FROM AUTHOR]

Most conventional algorithms for non-Lambertian photometric stereo can be partitioned into two categories. The first category is built upon stable outlier rejection techniques while assuming a dense Lambertian structure for the inliers, and thus performance degrades when general diffuse regions are present. The second utilizes complex reflectance representations and non-linear optimization over pixels to handle non-Lambertian surfaces, but does not explicitly account for shadows or other forms of corrupting outliers. In this paper, we present a purely pixel-wise photometric stereo method that stably and efficiently handles various non-Lambertian effects by assuming that appearances can be decomposed into a sparse, non-diffuse component (e.g., shadows, specularities, etc.) and a diffuse component represented by a monotonic function of the surface normal and lighting dot-product. This function is constructed using a piecewise linear approximation to the inverse diffuse model, leading to closed-form estimates of the surface normals and model parameters in the absence of non-diffuse corruptions. The latter are modeled as latent variables embedded within a hierarchical Bayesian model such that we may accurately compute the unknown surface normals while simultaneously separating diffuse from non-diffuse components. Extensive evaluations are performed that show state-of-the-art performance using both synthetic and real-world images. [ABSTRACT FROM AUTHOR]

Dense 3D reconstruction of fast moving objects could contribute to various applications such as body structure analysis, accident avoidance, and so on. In this paper, we propose a technique based on a one-shot scanning method, which reconstructs 3D shapes for each frame of a high frame-rate video capturing the scenes projected by a static pattern. To avoid instability of image processing, we restrict the number of colors used in the pattern to less than two. The proposed technique comprises (1) an efficient algorithm to eliminate ambiguity of projected parallel-line patterns by using intersection points, (2) a batch reconstruction algorithm of multiple frames by using spatio-temporal constraints, and (3) an efficient detection method of color-encoded grid pattern based on de Bruijn sequence. In the experiments, the line detection algorithm worked effectively and the dense reconstruction algorithm produces accurate and robust results. We also show the improved results by using temporal constraints. Finally, the dense reconstructions of fast moving objects in a high frame-rate video are presented. [ABSTRACT FROM AUTHOR]

An architecture of multiple-integrated converter modules sharing an unfolding full-bridge inverter with a pseudo dc link (MIPs) is proposed for grid-connected photovoltaic systems in this paper. The proposed configuration can improve the power conversion, the control circuit complexity, and the cost competitiveness. The proposed MIP is composed of distributed flyback dc–dc converters (DFCs) and an unfolding full-bridge inverter with an ac filter. The DFCs can eliminate the shading effect by using the individual maximum power point tracking. In conventional flyback-type single-phase utility-interactive inverters, discontinuous conduction mode and boundary conduction mode are popular because of the inherent constant current-source characteristics more desirable for grid connection and of the simple procedures for the controller design. However, the operating mode suffers from a large current stress of the circuit components, which leads to the low power efficiency. To avoid this, the DFCs operate under continuous conduction mode that allows reduced current stresses and increased power efficiency, as well as low material cost. The current control loop of the converters employs primary-side regulation contributing to improvement of dynamics as well as the cost reduction significantly due to the elimination of the high-linearity photocoupler device. Development of a new dc-current loop that maintains the level of dc-current injection into the grid within the levels stipulated by IEEE 1547 will be dealt as well. The performance validation of the proposed design is confirmed by experimental results of a 200-W hardware prototype. [ABSTRACT FROM PUBLISHER]

Data stream clustering provides insights into the underlying patterns of data flows. This paper focuses on selecting the best representatives from clusters of streaming data. There are two main challenges: how to cluster with the best representatives and how to handle the evolving patterns that are important characteristics of streaming data with dynamic distributions. We employ the Affinity Propagation (AP) algorithm presented in 2007 by Frey and Dueck for the first challenge, as it offers good guarantees of clustering optimality for selecting exemplars. The second challenging problem is solved by change detection. The presented StrAP algorithm combines AP with a statistical change point detection test; the clustering model is rebuilt whenever the test detects a change in the underlying data distribution. Besides the validation on two benchmark data sets, the presented algorithm is validated on a real-world application, monitoring the data flow of jobs submitted to the EGEE grid. [ABSTRACT FROM PUBLISHER]

Self-organisation provides a suitable paradigm for developing self-managed complex distributed systems, such as grid computing and sensor networks. In this paper, an integrative self-organisation mechanism is proposed. Unlike current related studies, which propose only a single principle of self-organisation, this mechanism synthesises the three principles of self-organisation: cloning/spawning, resource exchange and relation adaptation. Based on this mechanism, an agent can autonomously generate new agents when it is overloaded, exchange resources with other agents if necessary, and modify relations with other agents to achieve a better agent network structure. In this way, agents can adapt to dynamic environments. The proposed mechanism is evaluated through a comparison with three other approaches, each of which represents state-of-the-art research in each of the three self-organisation principles. Experimental results demonstrate that the proposed mechanism outperforms the three approaches in terms of the profit of individual agents and the entire agent network, the load-balancing among agents, and the time consumption to finish a simulation run. [ABSTRACT FROM PUBLISHER]

In this paper, a new finite element mortar approach with moving nonmatching overlapping grids is introduced. The bidirectional transfer of information between the fixed and moving subdomains is realized for each new position of the moving part. Two numerical examples are presented to support the theory: 1) an electrostatic problem with known solution, to state the optimality of the method and 2) an eddy current nondestructive testing configuration, to underline the flexibility and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]