By randomly mapping items and nodes to a common address space, most P2P index structures based on DHTs provide only exact match data look-ups. This compromises their use in data-oriented applications where more advanc...
详细信息
ISBN:
(纸本)9780889866386
By randomly mapping items and nodes to a common address space, most P2P index structures based on DHTs provide only exact match data look-ups. This compromises their use in data-oriented applications where more advanced query facilities, such as range queries, are needed. We have previously proposed a P2P index structure that refines the Chord DHT by mapping data items to the Chord address space in an order-preserving way. Load balancing of skewed data is then achieved deterministically by pulling nodes to zones where too many data items reside. However, based on Chord's underlying routing infrastructure, our previous solution can no longer ensure logarithmic routing cost when the node distribution over the address space becomes highly skewed. In this paper, we push our previous study one step further and propose a simple yet efficient refinement to Chord's routing component. By offering nodes more flexibility in the choice of their neighbors, our solution ensures logarithmic routing cost, with high probability. Most importantly, our solution is dynamic in the sense that it adapts to any node distribution, including highly adversarial ones.
In this paper, we present a new auction algorithm for the linear assignment problem, based on a new technique, called look-back bidding. The main idea is to keep local working sets of objects. It leads to significant ...
详细信息
ISBN:
(纸本)088986392X
In this paper, we present a new auction algorithm for the linear assignment problem, based on a new technique, called look-back bidding. The main idea is to keep local working sets of objects. It leads to significant performance gains both in sequential and distributed memory parallel versions. We give performance results of the new algorithm, called look-back auction algorithm, and compare its complexity with standard auction algorithms. In the parallel version, our new algorithm eliminates a substantial amount of interprocessor communication.
In this paper, we propose a distributed prioritized h-out of-k mutual exclusion algorithm for a mobile ad hoc network (MANET) with real-time or prioritized applications. The h-out of-k mutual exclusion problem is a ge...
详细信息
ISBN:
(纸本)088986392X
In this paper, we propose a distributed prioritized h-out of-k mutual exclusion algorithm for a mobile ad hoc network (MANET) with real-time or prioritized applications. The h-out of-k mutual exclusion problem is a generalization of the k-mutual exclusion problem and the mutual exclusion problem. The proposed algorithm is sensitive to link forming and link breaking and thus is suitable for a MANET. It is worthwhile to mention that the proposed algorithm can also be applied to distributedsystems consisting of stationary nodes that communicate with each other by exchanging messages over wired links.
We consider the problem of determining parallel complexity of solving banded triangular linear systems using substitution on a k-dimensional torus network. We present lower bounds on execution time for solving these s...
详细信息
ISBN:
(纸本)088986392X
We consider the problem of determining parallel complexity of solving banded triangular linear systems using substitution on a k-dimensional torus network. We present lower bounds on execution time for solving these systems, taking into account communication costs. Furthermore, optimal algorithms are designed.
High performance computingsystems and cluster computers are becoming so cost-effective that even small research groups can afford them. Hence, efforts to take advantage of these widely distributed resources are becom...
详细信息
High performance computingsystems and cluster computers are becoming so cost-effective that even small research groups can afford them. Hence, efforts to take advantage of these widely distributed resources are becoming popular. Although recent projects provide resource management and job scheduling to support groups of computational resources across the country working together on massive problems, they have not yet fully addressed how distributedparallel programs will communicate. Therefore, we propose a new paradigm to support cluster-to-cluster (C2C) communications, which handles run-time communications between parallel programs running on distributed clusters.
This paper presents comprehensive evaluations of parallel double Divide and Conquer for singular value decomposition on a super computer, HPC2500. For bidiagonal SVD, double Divide and Conquer was proposed. It first c...
详细信息
ISBN:
(纸本)9780889867048
This paper presents comprehensive evaluations of parallel double Divide and Conquer for singular value decomposition on a super computer, HPC2500. For bidiagonal SVD, double Divide and Conquer was proposed. It first computes singular values by a compact version of Divide and Conquer. The corresponding singular vectors are then computed by twisted factorization. The speed and accuracy of double Divide and Conquer are as good or even better than standard algorithms such as QR and the original Divide and Conquer. Moreover, it shows high scalability even on a PC cluster, distributed memory architecture. parallel algorithm of dDC and numerical results in some architectural options, matrix sizes and types on HPC2500, SMP cluster is shown.
For an initial study in divisible load scheduling, an optimal computing power allocation problem in a distributedparallelcomputing grid involving two sources and a sink is considered. The objective is to optimally a...
详细信息
ISBN:
(纸本)9780889868205
For an initial study in divisible load scheduling, an optimal computing power allocation problem in a distributedparallelcomputing grid involving two sources and a sink is considered. The objective is to optimally allocate the computing power of the sink in the grid in a such way that the total parallelcomputing finish time of the entire load is equalized to the sequential computing finish time while utilizing the full computing power. A numerical method to calculate the optimal adaptive computing power via a deterministic analysis is presented under several computing constraints. Performance of the computing power adaptation is modeled and evaluated. For performance evaluation, we define average computing finish time.
We introduce a new view of distributed computation, called the NavP view, under which a distributed program is composed of multiple sequential self-migrating threads called DSCs. In contrast with those in the conventi...
详细信息
ISBN:
(纸本)088986392X
We introduce a new view of distributed computation, called the NavP view, under which a distributed program is composed of multiple sequential self-migrating threads called DSCs. In contrast with those in the conventional SPMD style, programs developed in the NavP view exhibit the nice properties of algorithmic integrity and parallel program composition orthogonality, which make them clean and easy to develop and maintain. The NavP programs are also scalable. We use example code and performance data to demonstrate the advantages of using the NavP view for general purpose distributedparallel programming.
Data clustering is a common technique for data analysis, which is used in many fields, including machine learning, data mining, pattern recognition, image analysis and bioinformatics. Due to the continuous increase of...
详细信息
ISBN:
(纸本)9780889867048
Data clustering is a common technique for data analysis, which is used in many fields, including machine learning, data mining, pattern recognition, image analysis and bioinformatics. Due to the continuous increase of datasets size and the intensive computation of clustering algorithms when used for analyzing large datasets, developing of efficient clustering algorithms is needed for processing time reduction. This paper describes the design and implementation of a recently developed clustering algorithm RACAL [1], which is a RAdius based Clustering ALgorithm. The proposed parallel algorithm (PRACAL) has the ability to cluster large datasets of high dimensions in a reasonable time, which leads to a higher performance computing.
The HBSP(Heterogeneous Bulk-Synchronous parallel) model is an asynchronous parallelcomputing model, whose communication features are abstracted by some parameters. In this paper, we present parallel algorithms for th...
详细信息
ISBN:
(纸本)088986392X
The HBSP(Heterogeneous Bulk-Synchronous parallel) model is an asynchronous parallelcomputing model, whose communication features are abstracted by some parameters. In this paper, we present parallel algorithms for the n × n 2D-data partition on the HBSP model, and we also present a method converting the BSP algorithms processing with 2D-data into the HBSP algorithms. Using our converting method, some BSP algorithms such as matrix multiplication or all-pairs shortest paths can be converted into efficient HBSP algorithms.
暂无评论